\documentclass[11pt]{report}
\usepackage{stylefiles/smstc_mod,stylefiles/probability,color,mathrsfs}
%\usepackage{showkeys}
\usepackage{epsfig}
%% amsmath, amssymb, cite, fancybox, graphicx, ifthen, minitoc, url, xspace
\Streamname{Probability}  
\Unitname{} 
\Thisyear{2007/08}  
\AuthorFt{Takis Konstantopoulos}

%\newtheorem{exe}{Drill}
%\newtheorem{example}{Example}[section]
%\newtheorem{definition}{Definition}[section]
%\newtheorem{lemmaA}{Lemma A\!\!}
%\newtheorem{propositionA}{Proposition A\!\!}
%\newtheorem{theoremA}{Theorem A\!\!}
%\newtheorem{lemmaB}{Lemma B\!\!}
%\newtheorem{propositionB}{Proposition B\!\!}
%\newtheorem{theoremB}{Theorem B\!\!}
\theoremstyle{definition}
\newtheorem{exe}{\bf EXERCISE}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\FF{\mathscr{F}}
\def\GG{\mathscr{G}}
\def\HH{\mathscr{H}}
\def\DD{\mathscr{D}}
\def\CC{\mathscr{C}}
\def\RR{\mathscr{R}}
\def\G{\mathbb{G}}
\def\H{\mathbb{H}}
\def\xx{\widehat{x}}
\def\XX{\widehat{X}}
\def\AA{\mathscr{A}}
\def\SS{\mathscr{S}}
\def\TT{\mathscr{T}}
\def\BB{\mathscr{B}}
\def\VV{\mathscr{V}}
\def\LL{\mathcal{L}}
\def\NN{\mathcal{N}}
\def\Qr{\mathbf{Q}}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\1}{{\text{\Large $\mathfrak 1$}}}
\renewcommand{\comp}{\raisebox{0.1ex}{\scriptsize $\circ$}}
\newcommand{\cadlag}{{c\`adl\`ag} }
\renewcommand{\var}{\operatorname{var}}
\newcommand{\proj}{\operatorname{proj}}
\renewcommand{\cov}{\operatorname{cov}}
\renewcommand{\limsup}{\varlimsup}
\renewcommand{\liminf}{\varliminf}
\renewcommand{\d}{\text{\rm\,d}}
\newcommand{\eqdist}{\stackrel{\text{d}}{=}}
\newcommand{\dirac}{\text{\large $\mathfrak d$}}
\newcommand{\Ri}{\Rightarrow}
\def\iid{{i.i.d.}\xspace}
\def\jid{{i.i.d.}}
\def\ie{{i.e.}\xspace}
\def\eg{{e.g.}\xspace}
%A \xrightarrow[n]{} 0
\def\bigtimes{\text{\LARGE$\times$}}
\def\xor{\text{\footnotesize$\bigtriangleup$}}
\def\prob{\operatorname{\bf prob}}
\def\no{\noindent}

\parskip \smallskipamount
\parindent 5mm


\begin{document} \initdoc 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{3}{Random variables}

% SYLLABUS:
% Random variables and their distributions.				DONE
% Distribution functions, probability (mass) functions, DONE
% probability density functions, 	DONE
% moments, 	DONE
% simple inequalities  (Markov, Chebychev), 	DONE
% transformations.  	DONE
% Moment generating   functions (briefly).	DONE

%\noindent{\sf Organisation: This chapter contains simple exercises throughout
%the text, called ``drills'', and more substantial exercises at the end. The
%Glossary section summarises notation and basic maths needed. Without this
%kind of maths, there is no way you can learn Probability.}


\section{Introduction}
Random variables are at the core of Probability and Modern Mathematics
and have nothing to do with randomness: they are merely
functions, labels of outcomes of an ``abstract space'' $\Omega$.
These functions must be compatible with the set of events of $\Omega$.
This compatibility property is called measurability. The concept
of a random variable is purely functional. 

David Mumford \cite{dm} 
challenges the mathematical community by insisting that
we are encountering a paradigm shift in Mathematics, namely, we
are seeing how ``Stochasticity'' plays a much more fundamental
role within Mathematics than previously envisioned. 
Moreover, Mumford claims that random variables should be put
first in the discipline of Probability. Somehow, he suggests
a change of the neo-classical Kolmogorov foundation, and wants to
replace it by functions, i.e.\ random variables, as primary
objects.
There is no doubt that this can be done, just as Topology can 
be approached, not with sets, but with functions to start with.
While we will not be as ``radical'' as Mumford, we will explain
the importance of random variables by explicitly discussing all
(classical) nuances associated with them.

So we first start with functional concepts, ignoring probability.
We then put a probability and see how it is transformed by
a random variable: a random variable transforms a probability
into another probability that is known as its law.

Discrete random variables are trivial, from a foundational point of
view (but far from trivial otherwise).
Continuous random variables are hard to visualise. 
We prefer to construct such random variables. by flipping coins which
is the most natural thing to do in Probability
(arguably the only thing to do). 

The distribution of a random variable is any function that uniquely specifies
its law. It is a convention, for real random variables, to use the
so-called distribution function as a distribution.
Some distribution functions are nice in the sense that they
can be differentiated and their derivatives are useful
because they can be integrated to enable us to compute probabilities.
These derivatives are called densities. We try to be semi-honest
when discussing them.

The expectation of a random variable is discussed, constructed,
and shown to be compatible with the usual na\"ive formulae.

Some {\em sine qua non} inequalities (under the names of
Markov, Chebyshev, Chernoff, Jensen, Cauchy, Bunyakowskii, Schwarz,
H\"older and Minkowski) are presented, because inequalities are
more useful than equalities.

Finally, there is a brief discussion of he concept of a moment
generating function. 

Exercises are scattered within the text.

Appendix A summarises basic notions regarding sets.
Appendix B is gives a somewhat elementary approach to putting probabilities
on sets.





\section{Random variables are functions}

A measurable space is a set together with a
$\sigma$-field of subsets of it. 
The concept of a random variable was introduced
in \fbox{1.1.5}. Intuitively, a random variable assigns concrete labels
to abstract outcomes. Concretely,
\begin{quote}
{\sc A random variable is a measurable function}
 $X$ between two measurable spaces,
an ``abstract'' one, $(\Omega, \FF)$, and a ``concrete''\footnote{
The adjectives in quotes have nothing to do with Mathematics but, rather, with
our human interpretation of it. 
}
one, $(S, \SS)$.
\end{quote}
In other words, we require that the inverse image by $X$ of each element 
of $\SS$ be an element of $\FF$.
We denote this situation by 
\[
X : (\Omega, \FF) \to (S, \SS).
\]
Many a times $(\Omega, \FF)$ could (or should) be left unspecified but 
$(S, \SS)$ should be chosen specifically;
for example it could be $(\R, \BB)$, where $\BB=\BB(\R)$ is the class of
Borel sets  (see \fbox{1.1.3})
on $\R$. In such a case we call $X$ {\sc ONE (real) random variable},
omitting the numeral ONE when not necessary. As another example, let
$(S, \SS) = (\R^2, \BB(\R^2))$, where $\BB(\R^2)$ are the Borel sets on $\R^2$
(defined as the smallest $\sigma$-field containing all open sets in $\R^2$).
In this case we refer to $X$ as {\sc TWO (real) random variables}, because 
we may,
by choosing Cartesian co\"ordinates on $\R^2$, represent
$X$ by $(X_1, X_2)$, where $X_1$ is one random variable and $X_2$ is
also one random variable.
More generally, we may let $(S, \SS) =(\R^d, \BB(\R^d))$, and then
we refer to $X$ a {\sc random ($d$-dimensional real) vector}.

Terminology: we say that $X$ is a random variables IN $S$ or
that $X$ is a random element OF $S$.
If $S$ is a concrete space with a name ``abc'' then we call $X$ a random
``abc''. For instance, if $S$ is the space of triangles on the plane, then
a random variable in $X$ is called random triangle.


\begin{exe}
\label{drill1}
Show that if $X: (\Omega, \FF) \to (S, \SS)$, $H: (S, \SS) \to (T, \TT)$
are random variables then $H \comp X$ is a random variable.
\end{exe}

The following lemma, useful in checking that a function is a random variable:
\begin{lemma}
\label{bang}
If $X : \Omega \to S$ is a function, $\FF$ a $\sigma$-field on $\Omega$
and $\SS$ a  $\sigma$-field on $S$ generated by the collection of
sets $\CC$ then $X$ is a random variable if and only if 
$X^{-1}(B) \in \FF$ for all
$B \in \CC$.
\end{lemma}
\begin{proof}
Let $\SS' := \{ B \subset S:~ X^{-1}(B) \in \FF\}$.
This is a $\sigma$-field. Indeed, if $B \in \SS'$ then
$X^{-1}(B^c) = X^{-1}(B)^c \in \FF$ because $X^{-1}(B) \in \FF$.
If $B_1, B_2, \ldots \in \SS'$ then $X^{-1} (\cap_j B_j)
= \cap_j X^{-1}(B_j) \in \FF$ because each $X^{-1}(B_j) \in \FF$.
Suppose that $X^{-1}(B) \in \FF$ for all $B \in \CC$.
This means that $\CC$ is contained in $\SS'$.
But then $\SS$ which is the smallest $\sigma$-field containing $\CC$
must be contained in $\SS'$ for the latter is a $\sigma$-field.
In symbols, $\SS \subset \SS'$. But, by definition of $\SS'$, this means
that $X^{-1}(B) \in \FF$ for any $B \in \SS$.
\end{proof}

Recall that the notation
\[
\{X \in B\} = X^{-1}(B)
\]
is used all the time, so we will stick to it when we can.
\begin{corollary}
If $X: \Omega \to \R$ is a function and $\FF$ a $\sigma$-field on $\Omega$,
then $X$ is one random variable 
$\iff$ $\{X \le x\} \in \FF$ for all $x \in \R$
$\iff$ $\{X < x\} \in \FF$ for all $x \in \R$
$\iff$ $\{X > x\} \in \FF$ for all $x \in \R$.
\end{corollary}

The real fun starts when $(S, \SS)$ is chosen to be a large 
(but concrete) space, for example, $S$ can be a subset of
a space of real-valued functions on the real line and $\SS$ a suitable
$\sigma$-field. 
In such a case, $X$ is called {\sc random function} or {\sc stochastic process}
(stochastic being a synonym of random and process being a synonym
of function; therefore, random process or stochastic function
are also acceptable terminologies for the same thing).


\section{Continuous functions of random variables}
\begin{lemma}
If $X$ is a random vector in $\R^d$ and $f: \R^d \to \R^k$ is
a continuous function then $f \comp X$ is a random vector in $\R^k$.
\end{lemma}
\begin{proof}
Let $B$ be an open subset of $\R^k$. Then $f^{-1}(B)$ is an open
subset of $\R^d$ because $f$ is continuous. Hence $f^{-1}(B)$
is a Borel subset of $\R^d$ and so $f$ is measurable. Now use Exercise
\ref{drill1}.
\end{proof}

An application of this is that all usual algebraic operations
on random variables will result random variables. So
\[
X_1 + X_2,
\quad
X_1 \cdot X_2,
\quad
X_1 \wedge X_2
\]
are all random variables.




A more important result is that we can go beyond algebraic operations
and retain measurability. So
\begin{lemma}
\label{balg}
If $X_1, X_2, \ldots$ are random variables in $\R$ then
\[
\inf_j X_j, \quad \liminf_j X_j,
\quad
\sup_j X_j, \quad \limsup_j X_j
\]
are random variables in $\R \cup\{+\infty, -\infty\}$.
\end{lemma}
\begin{proof}
Indeed,
\[
\{\inf_j X_j \le a\} = \cap_j \{X_j \le a\}
\]
and, since $\{X_j \le a\} \in \FF$ for all $j$, and $\FF$ is a $\sigma$-field,
then the intersection also belongs to $\FF$.
For the second variable, we simply observe that $\sup_j X_j = - \inf_j (-X_j)$
is also a random variable and so $\liminf_j X_j = \sup_j \inf_{k \ge j} X_k$
is also a random variable.
\end{proof}


\section{Induced $\sigma$-fields; measurability}
Recall, as in \fbox{1.1.3}, that 
\begin{quote}
the $\sigma$-field generated by
a collection, say $\AA$ of subsets of $\Omega$, is defined as
the intersection of all $\sigma$-fields containing $\AA$; it
is denoted by $\sigma(\AA)$.
\end{quote}
If $X : \Omega \to S$ is a function, and if $\SS$ is 
a fixed $\sigma$-field on $S$,
the $\sigma$-field {\sc generated} or {\sc induced} by $X$ is defined by
\[
\sigma(X) := \{X^{-1}(B), B \in \SS\}.
\]
It is easy to see that 
\begin{lemma}
(i) $\sigma(X)$ is a $\sigma$-field,
(ii) $\sigma(X)$ is the intersection of all $\sigma$-fields
$\GG \subset \FF$ such that $X: (\Omega, \GG) \to (S, \SS)$ is 
a random variable,
(iii) $X$ is a random variable if and only if $\sigma(X) \subset \FF$.
\end{lemma}
If $Y: \Omega \mapsto S'$ is another function, and if $S'$ is endowed
with another fixed $\sigma$-field $\SS'$, 
then the notation $\sigma(X,Y)$ stands for the smallest
$\sigma$-field containing $\sigma(X)= \{X^{-1}(B), B \in \SS\}$ and 
$\sigma(Y)= \{X^{-1}(B), B \in \SS'\}$:
\[
\sigma(X,Y) := \sigma(\sigma(X) \cup \sigma(Y)) =: \sigma(X) \vee \sigma(Y).
\]
(The last bit is just another notation for the same thing.)
%
%$\star$ 
%At this point, the reader is advised to read Appendix A for the definition
%of products.
%
Let us study random variables that take values in $\R^d$ or, more generally,
in a product $S_1 \times \cdots \times S_d$ of sets.
Suppose that on each $S_i$ we have a $\sigma$-field $\SS_i \subset 2^{S_i}$.
We first construct a natural $\sigma$-field on  $S_1 \times \cdots \times S_d$.
For each $i$ consider the projection function
\[
\pi_i : S_1 \times \cdots \times S_d \to S_i; \quad
\pi_i : (s_1, \cdots, s_d) \mapsto s_i.
\]
Define 
\[
\SS_1 \otimes \cdots \otimes \SS_d := \sigma(\pi_1, \ldots, \pi_d).
\]
\begin{exe}
Consider $(S_i, \SS_i)$, $i=1, \ldots, d$. Let $d=2$ for simplicity.
Show that
\begin{align*}
\SS_1 \otimes \SS_2
&=
\sigma(
\{B_1 \times S_2: B_1 \in \SS_1\}
\cup
\{S_1 \times B_2: B_2 \in \SS_2\}).
\\
&= \sigma(\{B_1 \times B_2: B_1 \in \SS_1, B_2 \in \SS_2\}).
\end{align*}
\end{exe}
\begin{lemma}
Let $X_i : (\Omega, \FF) \to (S_i, \SS_i)$, $i=1,2, \ldots,d$,
be random variables.
Let $S= S_1 \times \cdots \times S_d$, 
$\SS = \SS_1 \otimes \cdots \otimes \SS_d$.
Then $(X_1, \ldots, X_d) : (\Omega, \FF) \to (S, \SS)$  is a random variable. 
%The $\sigma$-field generated by $(X_1, \ldots, X_d)$
%is, as above,
%\[
%\sigma(X_1, \ldots, X_d) = \{(X_1, \ldots, X_d)^{-1}(B), B \in \BB(\R^d)\}.
%\]
%Furthermore,
%\[
%\sigma(X_1, \ldots, X_d) = \sigma(X_1) \vee \cdots \vee \sigma(X_d).
%\]
\end{lemma}
\begin{proof}
We just have to check that $(X_1,\ldots,X_d)^{-1}(B) \in \FF$ for
$B$ ranging in a suitable $\pi$-system. We take this $\pi$-system
(and it is immediate to see that it is so)
to be all sets of the form $B_1 \times \cdots \times B_d$, 
where $B_j \in \SS_j$ for all $1 \le j \le d$.
Then $(X_1,\ldots,X_d)^{-1}(B_1 \times \cdots \times B_d)
= \{(X_1,\ldots,X_d) \in B_1 \times \cdots \times B_d\}
= \{X_1 \in B_1\} \cap \cdots \cap \{X_d \in B_d\} \in \FF$.
\end{proof}

Moreover, and more importantly for all the theory
of stochastic processes, we can carry this to infinity. 
Let $(S_i, \SS_i)$, $i=1,2,\ldots$, be measurable spaces.
We wish to consider the space $S = \times_{i=1}^\infty S_i$
and endow it with a natural $\sigma$-field $\SS$. To do so,
consider sets of the form $B_1 \times B_2 \times \cdots$\footnote{
Each such set is called `finite-dimensional rectangle'.
}
where $B_i \in \SS_i$ for all $i$, and where $B_j = S_j$ for
all but finitely many indices $j$.
Define $\SS = \bigotimes_{i=1}^\infty  \SS_i$
to be the smallest $\sigma$ field containing all these sets.
\begin{lemma}
Suppose that for each $i \in \N$,  $X_i: (\Omega, \FF) \to (S_i, \SS_i)$
is a random variable. 
Let $S = \bigtimes_{i=1}^\infty S_i$ and let $X=(X_1, X_2, \ldots):
(\Omega, \FF) \to (S, \SS)$, where $\SS = \bigotimes_{i=1}^\infty  \SS_i$
is the product-sigma field.
Then $X$ is a random variable.
%Moreover,
%\[
%\sigma(X_1, X_2, \ldots) = \bigvee_{i=1}^\infty \sigma(X_i)
%= \bigvee_{i=1}^\infty \bigvee_{k=1}^j \sigma(X_1, \ldots, X_k).
%\]
\end{lemma}
\begin{proof}
Consider the $\pi$-system consisting of sets of the form
$\cap_{i=1}^\infty B_i$ where $B_i \in \SS_i$ for all $i$,
and where $B_i = S_i$ for all but finitely many indices $i$.
\end{proof}

Now consider the set $\R^2$. The natural $\sigma$-field on it
if $\BB \otimes \BB$, usually denoted by $\BB(\R^2)$.
Similarly for $\R^d$.

We should view $\sigma(X)$ as the essential information contained in $X$.
We explain: If $\Omega$ is a set and $X : \Omega \to S$ a function then
just by looking at the values of $X$ we may not be able to distinguish
elements of $\Omega$, simply because $X$ may take the same value on
different points of $\Omega$. In other words, unless $X$ is one-to-one, 
the set $X(\Omega) = \{X(\omega), \omega \in \Omega\}$
contains ``less information'' than $\Omega$.
Take a trivial example: Let $\Omega =\{-N, -N+1, \ldots, N-1, N\}$, 
and let $X(i) = i^3$ for all $i \in \Omega$.
Then $X(\Omega)$ contains precisely
the same information as $\Omega$. But if $Y(i) = i^2$ then $Y(\Omega)$ is
less informative than $\Omega$ because the sign is lost.
In some sense, we are not interested in the exact values of a random
variable but only on whether the values can distinguish elements of $\Omega$.

Take an abstract set $\Omega$ (for example think of $\Omega$ as a square
in the 2-dimensional Euclidean plane), let $A \subset \Omega$ and consider
the random variable $\1_A$. This takes only two values, $0$ and $1$, so the
information conveyed by it is not that large. Indeed,
\[
\sigma(\1_A) = \{\varnothing, A, A^c, \Omega\}
\]
We may represent $\sigma(\1_A)$ as a partition of $\Omega$, the partition
consisting of $A$ and its complement. Thus, $\1_A$ can only tell
us whether we are on $A$ or on its complement: very little information indeed.
But we may as well use any function of $\1_A$ that does
not compress it further, for example, $c \cdot \1_A$, where $c$ is a nonzero
constant. 
\begin{exe}
\label{drill4}
Consider two subsets $A_1, A_2$ of $\Omega$ and prove that the 
$\sigma$-field generated by $c_1\1_{A_1} + c_2 \1_{A_2}$ is
\begin{multline*}
\sigma(c_1\1_{A_1} + c_2 \1_{A_2}) = 
\{\varnothing,~ \Omega,~
A_1,~ A_2,~ 
A_1^c,~ A_2^c,~ 
A_1A_2,~ A_1 A_2^c,~ A_1^c A_2,~ A_1^c A_2^c,~
\\
A_1 \cup A_2,~ A_1 \cup  A_2^c,~ A_1^c \cup  A_2,~ A_1^c \cup  A_2^c,~
A_1 \xor A_2,~
(A_1 \xor A_2)^c
\}.
\end{multline*}
\end{exe}
It is more convenient to represent this $\sigma$-field by the 
partition of $\Omega$ induced by $A_1, A_2$, i.e.\ by the
collection of disjoint sets
\[
\{
A_1 A_2, ~ A_1 \setminus A_2, ~ A_2 \setminus A_1, ~ (A_1 A_2)^c
\}.
\]
\begin{exe}
Any nonempty set in Exercise \ref{drill4} can be obtained as union of
elements of this partition.
\end{exe}
\begin{exe}
\label{drill6}
Given a partition $\CC =\{C_1, \ldots, C_n\}$ of $\Omega$ show that
the $\sigma$-field generated by $\CC$ consists of the empty set and
all sets that can be obtained by taking unions of sets in $\CC$.
Assuming that none of the $C_i$ is empty, this $\CC$ contains 
exactly $2^n$ sets.
Also show that any random variable that takes value $b_i$ on $C_i$ for each $i$
generates a $\sigma$-field which is contained in $\sigma(\CC)$. Show
that if the values $b_i$ are distinct then $\sigma(X) = \sigma(\CC)$.
\end{exe}

Unfortunately, this partition point of view does not carry over to
big spaces. It works well for finite $\Omega$ or for general $\Omega$ but
small $\sigma$-fields, but fails in richer situations. However, the intuition
obtained remains, in some sense, valid.
Let us explore this further.


If $X, Y$ are random variables on a common measurable space $(\Omega, \FF)$
(and values in arbitrary sets)
we say that {\sc $Y$ is measurable with respect to $X$} if 
\[
\sigma(Y) \subset \sigma(X).
\]
We often write this as
\[
Y \in \sigma(X).
\]
For example, if $X$ is one random variable then $X^2$ is measurable
with respect to $X$ (but not vice-versa); if
$(X_1, X_2, X_3)$ are three random variables then 
$(X_1, X_2)$ is measurable with respect to $(X_1, X_2, X_3)$ and
so is $(\cos(X_1 + X_2), - X_3 + \log|X_1|)$.
If it appears that 
\begin{quote}
``measurability with respect to'' means
``(suitable) function of'' 
\end{quote}
then this is because it really is so:
\begin{lemma}
\label{fof}
If $X: (\Omega, \FF) \to (S, \SS)$, $Y: (\Omega, \FF) \to (\R, \BB)$
are random variables, and if $Y \in \sigma(X)$, then
there exists a random variable (measurable map) 
$H: (S, \SS) \to (\R, \BB)$ such that $Y = H \comp X$.
\end{lemma}
(The proof is deferred until the next page or so.)
To understand why let us consider first a trivial situation: suppose
that $X$ takes only finitely many values; let $x_1, \ldots, x_n$ be these
(distinct) values.
\begin{exe}
Show that if $X(\Omega)=\{x_1, \ldots, x_n\}$ is a finite set
then $\sigma(X)$ is generated by the partition 
$\big\{\{X=x_i\}, ~ i=1,\ldots,n\big\}$ of $\Omega$.
\end{exe}
\begin{exe}
Using Exercise \ref{drill6} show that any $Y$, measurable with respect to
$X$, must be of the form
\[
Y = \sum_{i=1}^n c_i \1(X=x_i).
\]
\end{exe}
We then see that what is claimed in Lemma \ref{fof} is correct, in this
special situation with $X$ being finitely-valued. Indeed, let
$H(x) = \sum_{i=1}^n c_i \1(x=x_i)$ and, obviously, $Y = H \comp X$.


The general case requires an approximation result that says that
any measurable random variable $X: (\Omega, \FF) \to (\R, \BB)$ can
be approximated by simple random variables. A {\sc simple random
variable} is a random variable with finitely many values.
%\begin{exe}
%Show that a simple random variable $X:(\Omega, \FF) \to (\R, \BB)$
%is a random variable of the form
%\[
%X = \sum_{i=1}^k c_i \1_{A_i},
%\]
%where $c_i \in \R$, $A_i \in \FF$, $1\le i \le k$, $k \in \N$.
%Show that this representation may not be unique. However, if the
%sets are disjoint
%\end{exe}
\begin{lemma}
\label{sa}
Let $X : (\Omega, \FF) \to (\R, \BB)$. Then there exists
a sequence $X_1, X_2, \ldots$ of simple random variables such that
$\lim_{n\to\infty} X_n(\omega) = X(\omega)$.
If $X(\omega) \ge 0$, $\omega \in \Omega$, we can choose the sequence so that
$0 \le X_n(\omega) \le X_{n+1}(\omega)$ for each $n$ and $\omega$.
\end{lemma}
\begin{proof}
First suppose $X(\omega) \ge 0$ for all $\omega \in \Omega$.
Let $\lceil x\rceil$ denote the smallest integer $k$ such that 
$k \ge x$. Define
\begin{gather}
\label{tau}
\tau_n(x) := 2^{-n} \lceil 2^n x\rceil  \wedge n.\\
X_n(\omega):= \tau_n(X(\omega)). 
\end{gather}
That $X_n(\omega) \to X(\omega)$ as $n \to \infty$ is obvious.
Since $\lceil a \rceil \le a$ we have $2\lceil a \rceil \le \lceil 2a \rceil$
and so $2\lceil 2^n X \rceil \le \lceil 2^{n+1} X \rceil$. Dividing both sides with $2^{n+1}$
we have $2^{-n}\lceil 2^n X \rceil \le 2^{-n-1} \lceil 2^{n+1} X \rceil$ and so $X_n \le X_{n+1}$. 
Next do not place any requirement on the sign of $X$ but observe that
\[
X = X^+ - X^-.
\]
Then reduce to the previous case.
\end{proof}

\noindent{\bf Proof of Lemma \ref{fof} }
Suppose first that $Y=\1_A$ for some $A \in \FF$ and that $Y \in \sigma(X)$. 
This means that $A \in \sigma(X)$. By definition of $\sigma(X)$, there
is a $B \in \BB$ such that $A = X^{-1}(B)$. Define $H(x) =\1(x \in B)$,
$x \in \R$. Then $H(X(\omega)) = \1(X(\omega) \in B) = 
\1(\omega \in X^{-1}(B)) = \1(\omega \in A) = Y(\omega)$ and
so $H \comp X = Y$, as required.
Suppose next that $Y$ is a simple random variable. Thus $Y=\sum_{i=1}^k
c_i \1_{A_i}$ where $A_i \in \FF$. By the previous case, there
are $H_i :(S, \SS) \to (\R, \BB)$, such that $\1_{A_i} = H_i(X)$.
Define $H(x) = \sum_{i=1}^k c_i H_i(x)$. Then, clearly, $H(X) = Y$.
Finally, suppose that $Y: (\Omega, \FF) \to (\R, \BB)$ is a 
positive random variable. Then, by lemma \ref{sa}, we can find
simple $Y_n: (\Omega, \FF) \to (\R, \BB)$, for all $n \in \N$,
such that $Y = \sup_n Y_n$.
By the case analysed above, we have, for each $n$,
a measurable function $H_n$ such that $Y_n = H_n \comp X$.
Define $H = \sup_n H_n$. By Lemma \ref{balg}, $H$ is measurable.
Also, $H \comp X = (\sup_n H_n) \comp X
= \sup_n (H_n \comp X) = \sup_n Y_n = Y$, as required.
In the general case, write $Y = Y^+-Y^-$ and reduce to the above one.
$\Box$

\begin{exe}
Let $X$ be one random variable in $\R$. Show that $\sigma(X^2)$
is a strict subset of $\sigma(X)$. But show that $\sigma(2^X) = \sigma(X)$.
\end{exe}

\noindent{\bf Remark }
Lemma \ref{fof} is very important in enhancing our understanding of
measurability. Measurability, in Probability Theory (as well as in other
areas of Mathematics like Descriptive Set Theory) is not an abstract
notion but conveys precisely the idea of ``information'' contained in
a measurement. 
%When a physicist performs an experiment he does not
%want to distinguish between all of his subatomic particles but merely
%measure some
It should also be stressed that 
$Y$ in Lemma \ref{fof} does not have to be restricted to take values in $\R$.
It could very well be a random vector (values in $\R^d$) or, more
generally, a random element of a fairly arbitrary space known as 
Polish space. We shall not enter into such advanced details here.

%\begin{lemma}
%Let $(S, \SS)$ be a measurable space and $T$ an index set.
%Let $S^T$ be the set of functions from $T$ to $S$ equipped
%with the product $\sigma$-field $\SS^T = \bigotimes_{t \in T} \SS$.
%Let $V \subset S^T$. Let $\VV:=\{B \cap V:~ B \in \SS^T\}$.
%Let $\pi_t: S^T \to S$ be the projection function on the $t$-th coordinate,
%i.e.\ let $\pi_t(f_u, u \in T) = f_t$.
%Then $X: \Omega \to V$ is a random variable if and only if
%for all $t \in T$, $X_t = \pi_t(X): \Omega \to S$ is a random variable.
%\end{lemma}
%\begin{proof}
%See Exercise \ref{one}.
%\end{proof}
%
%\begin{exe}
%\label{one}
%Suppose that $(S_j, \SS_j)$ are measurable spaces, for all $j \in J$.
%Show that if $S=\prod_{j \in J} S_j$ then the cylinder $\sigma$-field $\SS$
%on $S$ is the smallest $\sigma$-field such that each projection map 
%$\pi_j : S \to S_j$ becomes measurable.
%In other words, $\SS = \bigvee_{j \in J} \sigma(\pi_j)$.
%\end{exe}


\section{Law of a random variable}
The reader will of course have noticed that 
\begin{quote}
the concept of ``random variable'' has nothing to 
do with randomness. 
\end{quote}
The adjective ``random'' is attached because, 
in addition to the above, we also consider some probability (measure) 
$\Pr$ on $(\Omega, \FF)$ .
As a mathematical definition, the concept of random variable is
purely functional.
So let us do that: let $\Pr$ be a probability on $(\Omega, \FF)$.
The {\sc distribution} or {\sc law}
of the random variable $X$ is a probability $\Pr_X$ on
$(S, \SS)$ which is induced, in the most natural fashion, by $X$:
\[
\Pr_X(B) = \Pr(X^{-1}(B)), \quad B \in \SS.
\]
Note that $\Pr_X$ depends on two functions: the function $\Pr$ and 
the function $X$. 
\begin{exe}
Show that if $(\Omega, \FF, \Pr)$ is a probability space
and $X: (\Omega, \FF) \to (S, \SS)$ a random variable then
$(S, \SS, \Pr_X)$ is a probability space.
Hence if $X$ is a random vector then $X_1$ is a random variable.
\end{exe}
\begin{exe}
With the notation of Exercise \ref{drill1}, show that the law of $H \comp X$
as a random variable on the probability space $(\Omega, \FF, \Pr)$ is
the same as the law of $H$ as a random variable on $(S, \SS, \Pr_X)$.
\end{exe}
So the role of a random variable is to transform an abstract probability space
into a concrete one.

In practise, one is often given\footnote{
Actually, one is seldom given anything. Either one derives something from
some basic principles/requirements or one performs an experiment 
whereby measurements are collected and a probability measure is 
stipulated. The latter is the subject of Statistics}
a probability measure $\Qr$ on some 
$(S, \SS)$ and one may (or may not)
want to construct a probability space $(\Omega, \FF, \Pr)$ and
a random variable $X:(\Omega, \FF) \to (S, \SS)$ such that $\Pr_X=\Pr$. 
In the absence of any further requirement we follow Occam's razor
and consider the so-called {\sc canonical construction}: take
$\Omega=S$, $\FF=\SS$, $\Pr=\Qr$ and let $X(\omega) \equiv \omega$.
Then, obviously, $\Pr_X = \Qr$.
If this appears to be silly then this is because it is. But silly things
are often quite useful. On the other hand, if other requirements are
needed to be satisfied, choosing the ``right'' probability space
and the ``right'' random variable is an art.
The freedom in the choice of probability space can be roughly compared
to the freedom of choice of an appropriate co\"ordinate system in $\R^3$
when dealing, e.g.\ with the solution of a certain physical problem expressed
in terms of a partial differential equation. For example, when we study
the motion of fluid in a cylinder we may want to choose cylindrical
co\"ordinates.





\section{Law of a discrete random variable}
\label{law}
A {\sc discrete random variable} $X : (\Omega, \FF) \to (S, \SS)$
is, by definition, one that takes countably many values.
In other words, if $\Pr$ is a probability on $(\Omega, \FF)$ then
$X$ is discrete if and only if there is a countable set $D \in \SS$
such that $\Pr(X \in D)=1$.
We also assume that $D$ and all its subsets are members of $\SS$.
Hence the law $\Pr_X$ of $X$ is a probability on $D$.
We know that a probability on a countable set $D$ can be defined by
defining its values on singletons. These values form the so-called (in baby
probability talk) {\sc probability mass function} (see \fbox{1.1.5}) 
%(a terminology which will become obsolete once adulthood is reached).
Thus, the probability mass function is
\[
p (x) 
= \Pr_X\{x\}
= \Pr(X =x) ,
\quad x \in D.
\]
Clearly, if $B \subset D$ then 
\[
\Pr_X(B) = \Pr_X\bigg(\bigcup_{x \in B} \{x\}\bigg) =
\sum_{x \in B} p(x).
\]
So $p$ is sufficient for computing $\Pr_X$.
\begin{example}
A box contains $n$ socks labelled 1 through $n$. 
Pick two socks at random and let $X$ be the pair of their labels.
Then $X$ is a discrete random variable taking values $(i,j)$ where
$1 \le i, j \le n$, $i \neq j$. The probability mass function is
\[
p(i,j) = 1/n(n-1).
\]
But what is the probability space? First, we should realise that we do not
necessarily need to consider it. Second, we should realise that the article
``the'' is wrong, for there are many choices for a probability space.
Having said that, a reasonable choice for $\Omega$ is the
set of permutations $\omega$ of $\{1, \ldots, n\}$, i.e.\
$\omega=(\omega_1, \ldots, \omega_n)$ where all the $\omega_i$ take
values in $\{1, \ldots, n\}$ and are distinct. The $\sigma$-field $\FF$ 
should be rich enough to contain all singletons, i.e.\ $\FF=2^\Omega$. The
probability  $\Pr$ should be defined as $\Pr(\{\omega\}) = 1/n!$ for all
$\omega$.
To be honest we should check that $p(i,j) = \Pr\{\omega\in \Omega: \omega_1=i,
\omega_2=j\}$.
We have 
\[
\Pr\{\omega\in \Omega: \omega_1=i, \omega_2=j\}
= \frac{1}{n!} ~\sharp \{\omega\in \Omega: \omega_1=i, \omega_2=j\}
= \frac{(n-1)!}{n!} = \frac{1}{n(n-1)},
\]
as required. So $(\Omega, \FF, \Pr)$ is a probability space,
$X$ is a random variable (check this!), $\Pr_X$ is its law,
and $p$ is its probability mass function.
\end{example}

\begin{example}
Consider the experiment of picking $k$ integers at random
(with replacement) from the set $\{1, \ldots, n\}$. Our
$(\Omega, \FF)$ here can be taken to be
\[
\Omega = \{1, \ldots, n\}^k, \quad \FF = 2^\Omega,
\]
and the probability corresponding to the experiment should be
defined as 
\[
\Pr\{(\omega_1, \ldots, \omega_k)\} = \frac{1}{n^k}.
\]
Note here that $\{(\omega_1, \ldots, \omega_k)\}$ is a set containing
a single point, namely the ordered $k$-tuple 
$\omega=(\omega_1, \ldots, \omega_k)$.
For more general sets $B$ we take, as required, $\Pr(B) = \sum_{\omega \in B}
\Pr\{\omega\} = \frac{\sharp B}{n^k}$.
Define a random variable representing the maximum number picked:
\[
X(\omega) = \max(\omega_1, \ldots, \omega_k).
\]
Clearly, $X$ takes values in $\{1, \ldots, n\}$ and trivially,
$X$ is a measurable function from $(\Omega, \FF)$ to $(\{1, \ldots, n\}, 
2^{\{1, \ldots, n\}})$. (The inverse image of a subset of $\{1, \ldots, n\}$
under $X$ is, of course, a subset of $\Omega$, i.e.\ an element of $\FF$.)
Let us compute the probability mass function for $X$.
For $x \in \{1,\ldots,n\}$ we have
\begin{align*}
p(x) &= \Pr(X^{-1}(x)) = \Pr(X = x) 
= \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k)=x\}
\\
&=  \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x
\text{ but } \max(\omega_1, \ldots, \omega_k) \not \le x-1\}
\\
&= \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x\}
- \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x-1\}
\\
&= \frac{1}{n^k} \sharp\{\omega \in \Omega:~ \omega_1\le x , \ldots, \omega_k \le x\}
-\frac{1}{n^k}  \sharp\{\omega \in \Omega:~ \omega_1 \le x-1, \ldots, \omega_k \le x-1\}
\\
&= \frac{x^k-(x-1)^k}{n^k}.
\end{align*}
\end{example}

%If we were to deal ONLY with discrete random variables then there would be
%no need to introduce many of the concepts introduced above. However, one
%soon realises that one has to move...
\begin{exe}
Suppose that the random variable $X$ takes $n$ distinct values (i.e.\
$X(\Omega)$ is a set with $n$ elements). Show that $\sigma(X)$ has
$2^{2^n}$ elements and describe (give a procedure for describing) them.
\end{exe}

\section{Tossing coins}
\label{toss}
Consider the experiment of flipping fair coins independently (see \fbox{2.2}). 
%Since
%we have not defined independence yet, it is only fair not to refer to it.
A coin takes 2 values, heads or tails with probability $1/2$ each.
%\footnote{
%But since I assume that every reader has seen the fact before, he or
%she will not find the definitions below unreasonable.}
Label heads by 1 and tails by 0. 
Let $\omega_1$ be outcome of the first toss, $\omega_2$ that of the second, etc.
We stipulate that:
\begin{description}
\item[]
A coin flipped $n$ times
yields a string $(\omega_1,\ldots,\omega_n)$ 
of $n$ 0s or 1s with probability $1/2^n$ each.
\end{description}
For example $(0,1,0)$ should have probability $1/8$, while $(1,1,0,0,1)$
should have probability $1/32$.
In other words, we are {\em trying} to define a probability $\Pr$ by
saying that the $\Pr$ of an event that specifies the first $n$ outcomes
completely should be $1/2^n$, for each $n \in \N$.
Consider our desire to find out when
we will get our first 1 (head), i.e.\ let 
\[
T = \inf\{n \in \N:~ \omega_n=1\}.
\]
This {\em appears} to be a random variable. But on which measurable space?
We cannot pick $\Omega$ to be $\{0,1\}^n$ for some finite $n$, because
we have no bound on $T$.
%But we feel that $T$ should be finite.
%So it seems reasonable to consider 
%\[
%\Omega_0 = \bigcup_{n=1}^\infty \{0,1\}^n.
%\]
%(Remember the indexing convention: $\infty$ is not part of the index set--see
%Glossary.)
%$\Omega_0$ is a countable set because it is countable union of finite sets.
%We can thus define $\Pr$ by definining $\Pr$ on each singleton. We've done
%that:
%\[
%\Pr(\omega_1, \ldots, \omega_n) = 2^{-n}, \quad n \in \N.
%\]
%Since $\sum_{n=1}^\infty 2^{-n} = 1$, $\Pr$ is a probability measure
%on $(\Omega_0, 2^{\Omega_0})$.
%Notice that $\Omega$ is the union of disjoint sets. Indeed
%$\{0,1\}^n \cap \{0,1\}^m = \varnothing$ if $n \neq m$.
%So any function $T(\omega)$ is defined by definining what it equals to
%for all $\omega \in \{0,1\}^n$, and for all $n \in \N$.
%Well, we can define
%\[
%T\(\omega_1, \ldots, \omega_n) =
%\begin{cases}
%\infty 
%\min\{1 \le k \le n:~ \omega_k=1\}, & \text{ if }
%\end{cases}
%\]
We can, however, pick 
\[
\Omega = \{0,1\}^\N,
\]
i.e.\ the set of
all infinite-length sequences $\omega=(\omega_1, \omega_2, \ldots)$,
where $\omega_n =0 $ or $1$ for all $n$.
This is our {\sc coin-flip space}.
\begin{exe}
Show that the coin-flip space $\{0,1\}^\N$ is uncountable.
\end{exe}
To put what we said in some notation, let 
\[
R(i_1, \ldots, i_n) := \{ \omega \in \Omega:~
\omega_1 = i_1, \ldots, \omega_n=i_n\}.
\]
To this set we should assign probability $2^{-n}$:
\begin{equation}
\label{int}
\operatorname{\bf prob} (R(i_1, \ldots, i_n) ) = 2^{-n}.
\end{equation}
We use the symbol $\prob$ rather than $\Pr$ because we have not yet
verified that this is a probability.
%Try to understand $R(i_1, \ldots, i_n)$ means. It is the set (event)
%that the first coin toss give $i_1$, the second $i_2$, and so on, until
%the $n$-th toss which gives $i_n$. 
%For example, $R(0,1,1)$ means 
%that the first three tosses are ``tails, heads, heads''.
Let $\RR$ be the class of such sets (together with the empty set):
\[
\RR := \{\varnothing\} \cup \{R(i_1, \ldots, i_n):~
i_1, \ldots, i_n \in \{0,1\},~ n \in \N \}.
\]
Formula \eqref{int}  defines the  function
\[
\prob : \RR \to \R.
\]
It is by no means true that 
$\RR$ contains all subsets of $\Omega$ (far from that):
\begin{exe}
Show that 
\[
R(1) \cup
R(0,1) \cup
R(0,0,1) \cup \cdots \not \in \RR.
\]
Show that this set is the set $\{\omega\in \Omega: ~ T(\omega) < \infty\}$.
Show that the intersection of two elements of $\RR$ is in $\RR$, but
not the union.
\end{exe}
%Indeed, suppose $n \le m$,
%and consider $C_{i_1, \ldots, i_n} \cap C_{j_1, \ldots, j_m}$. This is
%$\varnothing$ unless $(i_1, \ldots, i_n) = (j_1, \ldots, j_n)$, in which case
%it is equal to $C_{i_1, \ldots, i_n, j_{n+1}, \ldots, j_m}$.
\begin{exe}
\label{drill12}
Second, the complement of any set in $\RR$ is written as a finite disjoint
union of sets in $\RR$.
(For example $R(0,1)^c = \{\omega: \omega_1=1\} \cup \{\omega: \omega_2=0\}
= R(1) \cup \{\omega: \omega_2=0\} = R(1) \cup R(1,0) \cup R(0,0)$.)
\end{exe}
What kind of properties does $\prob$ have? We would like $\prob$ to be, at least,
additive, i.e.\ to satisfy 
%the probability formula\footnote{
%``Total Probability Formula'' is another name for ``Finite Additivity''.}
$\prob(G_1 \cup \cdots \cup G_k)  = \prob(G_1)+\cdots+\prob(G_k)$
if $G_1, \ldots G_k$ are mutually disjoint elements of $\RR$.
There is an issue here: as we saw, the union of elements
of $\RR$ may not be in $\RR$.  So this last additivity property is
completely meaningless for $\prob$. We remedy this by enlarging $\RR$:
\[
\CC := \{G_1\cup \cdots \cup G_k:~ G_1, \ldots, G_k \text{ are mutually
disjoint elements of } \RR, ~ k \in \N\},
\]
and by extending $\prob$ to $\CC$ in the most natural way:
\[
\Pr_0(G_1\cup \cdots \cup G_k) := \sum_{j=1}^k \prob(G_j).
\]
\begin{lemma}
\label{exta}
(i) $\CC$ is a field.
(ii) $\Pr_0$ is well-defined and additive over $\CC$. 
\end{lemma}
\begin{proof}
(i)  Let $A, B \in \CC$. Then $A = \cup_{i=1}^n G_i$, 
$B = \cup_{j=1}^m H_j$,
where the $G_i$ are mutually disjoint (m.d.) elements of $\CC$,
and so are the $H_j$.
We have 
\[
A B = \cup_{i,j} G_i H_j
\]
and, clearly, the $G_iH_j$ are m.d.\ elements of $\RR$; so $AB \in \CC$.
Also, 
\[
A^c = \cap_j G_i^c,
\]
each $G_i^c$ is an element of $\CC$ (Exercise \ref{drill12}), and because
we just proved that $\CC$ is closed under intersections, we have 
$A^c \in \CC$. So $\CC$ is a field.
\\
(ii)
To show that $\Pr_0$ is well-defined means to show that if we can
write the same $A \in \CC$ in two different ways, say
$A= \cup_{i=1}^n G_i = \cup_{j=1}^m H_j$ where both the $G_i$ and the
$H_j$ are m.d.\ elements of $\RR$, we have
$\sum_i \prob(G_i) = \sum_j \prob(H_j)$.
But notice that $G_i = \cup_j G_i H_j$ and so
$\prob(G_i) = \sum_j \prob(G_i H_j)$,
and, similarly, 
$\prob(H_j) = \sum_i \prob(G_i H_j)$. This proves the claim that $\Pr_0$
is well-defined on $\CC$. Now, to show additivity, suppose that
$A_1, \ldots, A_n$ are m.d.\ elements of $\CC$. We must show that
$\Pr_0(\cup_i) = \sum_i \Pr_0(A_i)$.
%Indeed, fix $i_1, \ldots, i_n \in \{0,1\}$  and notice that
%$\big\{C_{i_1, \ldots, i_n; j_1, \ldots, j_m}, ~ j_1, \ldots, j_m \in \{0,1\}\big\}$
%are mutually disjoint with 
%\[
%C_{i_1, \ldots, i_n} = \bigcup_{j_1, \ldots, j_m}C_{i_1, \ldots, i_n; j_1, \ldots, j_m}.
%\]
%But $\prob(C_{i_1, \ldots, i_n; j_1, \ldots, j_m}) = 2^{-n-m}$
%and $\sum_{j_1, \ldots, j_m}  2^{-n-m} = 2^m  2^{-n-m} = 2^{-n}
%= \Pr(C_{i_1, \ldots, i_n})$.
Now, to show additivity, suppose that
$A_1, \ldots, A_n$ are m.d.\ elements of $\CC$. We must show that
$\Pr_0(\cup_i A_i) = \sum_i \Pr_0(A_i)$.
But each $A_i$ is itself a finite union of m.d.\ elements of $\RR$,
say $A_i = \cup_j H_{ij}$, and, by the definition of $\Pr_0$, we have
$\Pr_0(A_i) = \sum_j \prob(H_{ij})$.
So 
$\sum_i \Pr_0(A_i) = \sum_i \sum_j \prob(H_{ij})$.
On the other hand, $\cup_i A_i = \cup_{i,j} H_{ij}$ and the
$H_{ij}$ are m.d.\ elements of $\RR$. Hence, by the definition
of $\Pr_0$ again, we have $\Pr_0(\cup_i A_i) =  \sum_i \sum_j \prob(H_{ij})$.
\end{proof}

To put in words, what we have shown so far is that,
starting merely from the intuitive definition \eqref{int},
we can compute probabilities of sets that can be expressed 
using finitely many outcomes, i.e.\ that involve $\omega_i$
up to some finite index.
Mathematically, Lemma \ref{exta} has enabled us to define
a function
\[
\Pr_0: \CC \to \R
\]
in such a way that
\[
\Pr_0(G) = \prob(G), \quad \text { if }
G \in \RR
\]
and
\[
\Pr_0(G_1 \cup \cdots \cup G_k)  = \Pr_0(G_1)+\cdots+\Pr_0(G_k),
\quad \text{if $G_1, \ldots G_k$ are mutually disjoint elements of $\RR$}
\]
(a property which, as remarked, is meaningless for $\prob$).


But there are many sets, whose probability we would like to know,
but which do not belong to $\CC$. 
\begin{example}
The following (useful) sets do not belong to $\CC$:
\\
(i)
$A_1:= \displaystyle \{\omega:~ T(\omega) < \infty\}$
(i.e.\ the event that a head will occur at some point). Indeed, this
equals $\cup_{n=1}^\infty \{\omega\in \Omega:~\omega_n=1\}$ and does not 
belong to $\CC$ because it involves infinitely many coordinates.
\\
(ii)
$A_2:=\displaystyle \{\omega: \omega_n = 1 \text{ for infinitely many } n\}$.
This, obviously, does not belong to $\CC$. Formally the set equals
\[
\displaystyle \{\omega:~ \forall n ~ \exists m \ge n ~ \omega_m=1\}
= \bigcap_n \bigcup_{m \ge n} 
\{\omega:~ \omega_m=1\}
= \bigcap_n \bigcup_{m \ge n} \bigcup_{i_1,\ldots,i_m \in \{0,1\}}
R(i_1, \ldots, i_{m-1},1).
\]
And so it is explicitly seen that we need infinitely many sets
from $\RR$ to construct $A_2$.
\\
Although we feel that both $A_1$ and $A_2$ should be assigned probability
$1$, we {\em cannot} write $\Pr_0(A_1)=1$, neither $\Pr_0(A_2)=1$,
simply because neither of the two sets belongs to the domain of the function
$\Pr_0$.
\end{example}
So our desire to deal with these sets (and not only!)
forces us to carry the story further.


We saw (Lemma \ref{exta} that $\Pr_0$ is additive on $\CC$.
But more is true:
\begin{lemma}
\label{extb}
$\Pr_0$ is countably additive over $\CC$, that is,
if $G_n$ are mutually disjoint elements of $\CC$ and if $\cup_n
G_n \in \CC$ then $\Pr_0(\cup_n G_n) = \sum_n \Pr_0(G_n)$.
\end{lemma}
\begin{proof}
By Lemma [CA], Appendix B, it suffices to show that if $G_n$
is a decreasing sequence of elements of $\CC$ such
that $\cap_n G_n = \varnothing$ then $\Pr_0(G_n) \to 0$.
-- To be continued --
\end{proof}

We next consider the class $D(\CC)$
of sets that are limits of sequences of sets in $\CC$.
{Lemma \small [FIRST EXTENSION]}, Appendix B, shows that
we can define $\Pr_1$ on $D(\CC)$ such that $\Pr_1$ is countably
additive and agrees with $\Pr_0$ on $\CC$.

We then consider the class $D^2(\CC) = D(D(\CC))$
of sets that are limits of sequences of sets in $D(\CC)$.
Just as above, we can define $\Pr_2$ on $D^2(\CC)$ such that 
$\Pr_2$ is countably additive and agrees with $\Pr_1$ on $D(\CC)$.

One would suspect that by continuing, in this manner, by induction,
i.e.\ by taking sets which are limits of limits of limits, ad infinitum,
we would exhaust the class
\begin{equation}
\label{FF1}
\FF = \text{$\sigma$-field generated by } \CC.
\end{equation}
(It is not difficult to see that, also,
\begin{equation}
\label{FF2}
\FF = \text{$\sigma$-field generated by } \RR.)
\end{equation}
Unfortunately, this does not work. The way out is to do
as in {Proposition \small [SANDWICH]}, Appendix B. This proposition 
actually  proves the following:
\begin{theorem}
\label{ouf}
Let $\Omega = \{0,1\}^\N$.  Let $\RR$ be the class of sets of
the form $R(i_1, \ldots,i_n)
:=\{ \omega \in \Omega:~ \omega_1 = i_1, \ldots, \omega_n=i_n\}$.
Define $\prob(R(i_1, \ldots,i_n))=2^{-n}$. 
Let $\FF$ be the $\sigma$-field generated by $\RR$. 
Then there exists a UNIQUE probability $\Pr$ on $(\Omega, \FF)$
such that $\Pr(G) = \prob(G)$ for every $G \in \RR$.
\end{theorem}
\begin{proof}
See proof of  {Proposition \small [SANDWICH]}, Appendix B.
To prove uniqueness, assume that there is another probability
$\widetilde{\Pr}$ on $(\Omega, \FF)$ that agrees with $\prob$
on $\RR$. Then $\widetilde{\Pr}$ agrees with $\prob$ (and hence with
$\Pr$ on $\CC$. Let us define the class common domain of
$\Pr$, $\widetilde{\Pr}$:
\[
\DD := \{A \in 2^\Omega:~ \Pr(A) = \widetilde{\Pr}(A)\}.
\]
We have
\[
\CC \subset \DD.
\]
Therefore, of $\lambda(\CC)$ (resp.\ $\lambda(\DD)$)
is the smallest $\lambda$-system containing $\CC$ (resp.\ $\DD$)
we have
\[
\lambda(\CC) \subset \lambda(\DD).
\]
But it is easy to see that $\DD$ is itself closed under proper
differences and increasing limits. Therefore $\lambda(\DD) = \DD$.
On the other hand, by Lemma [Sierpi\'nski-Dynkin], Appendix B,
we have $\lambda(\CC) = \sigma(\CC)$. So $\FF:=\sigma(\CC)$ is contained
in $\DD$. In other words, the two probabilities agree on $\FF$.
\end{proof}

%
%For details of THIS proof, see, e.g.\ \cite{fg}.
%For a classical approach, see, e.g.\ \cite{wil}.



This theorem tells us that 
\begin{center}
\fbox{$(\{0,1\}^\N, \FF, \Pr)$ is a probability space.}
\end{center}
So we can use all the good things we know about a probability space.
For example, $T(\omega) = \inf\{n \in \N:~ \omega_n=1\}$ defines
a measurable function $T: (\Omega, \FF) \to (\R, \BB)$ and,
since $\{T \le n\}$ are increasing sets with union equal to the 
set $\{T < \infty\}$, we have $\Pr(T< \infty) = \lim_{n\to\infty}
\Pr(T \le n)$. But $\{T > n\} = R(0,\ldots,0)$ ($n$ 0's inside the parenthesis)
and  so $\Pr(T>n) = \prob(R(0,\ldots,0)) = 2^{-n}$. Thus $\Pr(T< \infty)
= \lim_n (1-2^{-n})=1$.


\begin{exe}
Consider the space $\Omega=\{0,1\}^\N$ and the class of sets $\RR$ defined
in the tossing coins section.
(i) Show that $\RR$ is a countable set, i.e.\
there is a one-to-one correspondence between $\RR$ and $\N$. (ii) Show that $\CC$ is the field generated by $\RR$ and is also countable.
(iii) Consider $\FF$, the $\sigma$-field generated by $\RR$ (and also by
$\CC$) and show that it is uncountable; more specifically, show that
there is a one-to-one correspondence between $\FF$ and $2^\N$.
(iv) Consider the class $2^\Omega$ of all subsets of $\Omega$ and show that
there is a one-to-one correspondence between $2^\Omega$ and
$2^{2^\N}$ (the class of subsets of the set of subsets of $\N$.)
It is known \cite{kf} that the cardinality
of the set of subsets of a set is strictly larger than
the cardinality of the set itself (Schroeder-Bernstein theorem). 
Using this, conclude that there $2^\Omega$ is strictly
larger than $\FF$. In fact MUCH larger: In some sense, most subsets of
$\Omega$ are outside $\FF$! This means that most sets of sequences
of coin tosses cannot be expressed using countably many operations on
elementary sets (i.e.\ sets from $\RR$). The CURIOUS thing though is
that we know very few of these sets: although the majority of them
are outside $\FF$, somehow, it is very heard to come up with an example.\footnote{In some sense, this exercise is a baby version of G\"odel's theorem which says, naively speaking, that most theorems cannot be proved. Except that
we hardly ever encounter them.}
\end{exe}






\section{Uniform random variable}
We will now construct our first non-discrete random variable.
Consider the probability space $(\Omega=\{0,1\}^\N, \FF, \Pr)$
of the coin tossing experiment. Define
\begin{equation}
\label{U}
U(\omega) = 
\frac{\omega_1}{2} +
\frac{\omega_2}{2^2} +
\frac{\omega_3}{2^3} + \cdots = \sum_{k=1}^\infty \frac{\omega_k}{2^k}.
\end{equation}
Let $U_n(\omega) := \sum_{k=1}^n \frac{\omega_k}{2^k}$: these are simple
random variables. Since 
$U(\omega) = \lim_{n \to \infty} U_n(\omega)$, we have, by Lemma \ref{balg},
that $U: (\Omega, \FF) \to (\R, \BB)$ is measurable (i.e.\ a random
variable). It is ONE random variable because it takes values in $\R$.
More specifically, observe that
\[
0 \le U(\omega) \le \sum_{k=1}^\infty \frac{1}{2^k} = 1.
\]
So $U(\Omega) \subset [0, 1]$.
Our first observation is
\begin{lemma} 
\label{dyad}
For any integer $0 \le a < 2^n$ and any $n \in \N$, unless
$\omega_i=1$ for all $i > n$,
\[
U \ge \frac{a}{2^n} \iff U_n \ge \frac{a}{2^n}.
\]
\end{lemma}
\begin{proof}
Note that $2^n U_n$ is an integer. If it is not the case
that $\omega_i=1$ for all $i > n$
we have $2^n U - 2^n U_n < 1$,
i.e.\ the integer part of $2^n U$ equals $2^n U_n$
and hence $2^n U \ge a$ iff $2^n U_n \ge a$.
\end{proof}

Next, we compute the following probabilities:
\begin{lemma}
For any integer $0 \le a < 2^n$ and any $n \in \N$, we have
\[
\Pr(U \le a/2^n) = a/2^n.
\]
\end{lemma}
\begin{proof}
%First observe that $\Pr(U=b/2^n)=0$ for any integer $b \le 2^n$.
%To see this notice that if $b < 2^n$ and $U(\omega) = b/2^n$ then, necessarily,
%$\omega_i=0$ for all $i \ge n+1$. But the latter event is
%the limit of the events
%\[
%\{\omega \in \Omega:~ \omega_{n+1}= \cdots = \omega_\ell=0\},
%\quad \ell > n,
%\]
%as $\ell \to \infty$. The probability of these events is $2^{-(\ell-n)}$ which
%tends to $0$ as $\ell \to \infty$. Hence $\Pr(U=b/2^n)=0$.
%If $b = 2^n$ then $b/2^n=1$ and, for the same reason, $\Pr(U=1)=0$.
%Using this and Lemma \ref{dyad} we find that
Using Lemma \ref{dyad} we find that
\[
\Pr(U < a/2^n) = \Pr(U_n < a/2^n).
\]
%We prove that $\Pr(U_n \le a/2^n) = a/2^n$, for all $a < 2^n$, 
We use induction on $n$.
To start, let $n=1$.
Observe that $\Pr(U_1 < 1/2) = \Pr(\omega_1=0)=1/2$, as required.
Now assume the statement to be true up to index $n-1$.
Write
\begin{align*}
U_n(\omega) &= \frac{\omega_1}{2} + \frac{1}{2} Y_{n-1}(\omega),
\\
Y_{n-1}(\omega) &= \frac{\omega_2}{2} + \frac{\omega_3}{2^2} + \cdots
+ \frac{\omega_{n-1}}{2^{n-1}}.
\end{align*}
Therefore
\begin{align*}
\Pr(U_n < a/2^n) 
&= \Pr(\omega_1=0,~ Y_{n-1} < a/2^{n-1})
+
\Pr(\omega_1=1,~ Y_{n-1} < a/2^{n-1}-1)
\\
&= \tfrac{1}{2} \Pr(Y_{n-1} < a/2^{n-1}) +
\tfrac{1}{2} \Pr(Y_{n-1} < a/2^{n-1}-1).
\end{align*}
By the induction hypothesis, $\Pr(Y_{n-1} < c/2^{n-1}) = c/2^{n-1}$
for all $c < 2^{n-1}$ (why?).
If $a \le 2^{n-1}$, the second term in the display is $0$ and
the first equals $(1/2) \times (a/2^{n-1}) = a/2^n$, as needed.
If $2^{n-1} < a < 2^n$, the first term equals $1/2$ and the second
equals $(1/2) \times (a/2^{n-1}-1)$; the sum gives again $a/2^n$.
\end{proof}

Finally, we have
\begin{lemma}
\label{udf}
For any real number $x \in [0,1]$,
\[
\Pr(U < x)
=
\Pr(U \le x) = x.
\]
\end{lemma}
\begin{proof}
%There is nothing to prove actually when $x$ is of the form $a/2^n$
%where $a$ is integer: it was proved earlier. So suppose $x$ is not
%of this form. 
Let $[y]$ denote the largest integer not exceeding
the real number $y$. Define, recursively,
\begin{gather*}
z_1=x, \quad \xi_1=[2z],\\
z_{n+1} = z_n - \frac{\xi_n}{2^n}, \quad
\xi_{n+1} = [ 2^{n+1} z_{n+1}].
\end{gather*}
We have $2^n z_{n+1} = 2^n z_n - \xi_n =
2^n z_n - [2^n z_n] \le 1$, so $z_{n+1} \le 1/2^n$ for all $n$.
Therefore the sequence $z_n$ converges to $0$ and the numbers $\xi_n$
are either $0$ or $1$.
We also have
\[
x_n:=
\frac{\xi_1}{2} +
\frac{\xi_2}{2^2} +
\cdots +
\frac{\xi_n}{2^n} 
=(z_1-z_2)+(z_2-z_3) + \cdots + (z_n-z_{n_+1}) = x-z_{n+1},
\]
and so $x_n \to x$, as $n \to \infty$. Also, $x_n$ is of the
form $a/2^n$, where $a$ is an integer.
So $\Pr(U \le x_n) = x_n$. Since $x_n$ actually increases to $x$,
we have $\cup_{n=1}^\infty \{U \le x_n\} = \{U < x\}$, and
so taking limits we get $\Pr(U < x) = x$, for all $x \le 1$.
This also implies $\Pr(U \le x+1/n) = x+1/n$ for all $n$ sufficiently
large. But $\cap_n \{U \le x+1/n\} = \{ U \le x\}$ and so, taking limits,
$\Pr(U \le x) = x$.
\end{proof}
\begin{corollary}
\[
\Pr(U=x) =0, \text{ for all } x \in [0, 1].
\]
\end{corollary}
So the random variable $U$ takes no specific value with positive probability.
Yet, $U$ exists (we constructed it). 
This is curious, but we can (must)
get used to it. 
Any real random variable with this property
is called {\sc continuous random variable}. 
In books, $U$ has a name: it is called {\sc 
uniform random variable on the interval $[0,1]$}.
\begin{corollary}
Let $\Q$ be the set of all rational numbers in $[0,1]$.
Then
\[
\Pr(U \in \Q) = 0.
\]
\end{corollary}
\begin{proof}
The set $\Q$ is enumerable (has countably many points). Hence
\[
\Pr(U \in \Q) = \Pr( \cup_{q \in \Q} \{ U =q\})
= \sum_{q \in \Q} \Pr(U=q) = 0.
\]
\end{proof}





\section{Probability, revisited}
Recall, once more, that a probability $\Pr$ defined on a $\sigma$-field
$\FF$ of subsets of a set $\Omega$ is a function $\Pr: \FF \to \R$
such that (i) $\Pr(\Omega)=1$, and (ii) $\Pr(\cup_n A_n) = \sum_n \Pr(A_n)$,
if the $A_n$ are mutually disjoint elements of $\FF$.

If $\Omega$ is a countable set then we know that it suffices to define $\Pr$
on singletons, i.e.\ knowledge of $\Pr\{\omega\}$ for all $\omega \in \Omega$
implies knowledge of $\Pr(A)$ for all $A \in \FF$. Indeed,
\[
\Pr(A) = \sum_{\omega \in A} \Pr\{\omega\}.
\]
We saw, in the previous section, the necessity to define $\Pr$ on sets
which are not countable. Can't we define $\Pr\{\omega\}$ for
all $\omega$ in this case? The argument is simple. Suppose we did do so.
Let $\Omega_+ := \{\omega \in \Omega:~ \Pr\{\omega\} > 0\}$, and,
for each $n \in \N$,
$\Omega_n = \{\omega \in \Omega:~ \Pr\{\omega\} \ge 1/n\}$.
This is a finite set with at most $n$ points.
Observe that $\cup_n \Omega_n = \Omega_+$. But this tells us that 
$\Omega_+$ is a countable set.
So this poses a ``philosophical'' problem: If we want to define
a random variable that is uniformly distributed on the uncountable set
$[0,1]$ by defining probabilities of singletons,
then we'd have to pick a countable subset of $[0,1]$ and define probabilities
of points there. But which one to pick? We cannot give preference to
any particular countable subset. 

The way out is not to define probabilities on single points, but, rather,
on sets, as we did in the previous section. We then do not give preference
to any particular countable subset, but we lose something ``intuitive'':
we assign zero probability to every individual point.
This is what needs to be done, both for physical and mathematical reasons,
and this is what shall be done hereafter: We will be defining
probabilities on sets.

But another burden appears now: whereas, in the countable case,
 we were free to define probabilities of points at will (as long as
they summed up to something finite), in the general case we cannot define
probabilities of sets at will: we must respect the countable additivity
property (ii) above. 
Since there are far too many sets, we will try to see how to define
$\Pr$ on a class of selected few of them. So read the next section.




\section{Distribution functions}
Consider a real random variable $X: (\Omega, \FF) \to (\R, \BB)$
and put a probability $\Pr$ on $\Omega$. Recall the definition of
the law $\Pr_X$ of $X$:
\[
\Pr_X(B) = \Pr(X \in B), \quad B \in \BB.
\]
Up until the middle of the 19th century, a function was an object that
was given by a formula. Nowadays, of course, a function is more abstract: we
certainly need no formulae to comprehend what a function is. However, let
us take the old-fashioned point of view. Clearly, $\Pr_X$ is a function
whose arguments are sets (elements of $\BB$). These are a lot of arguments!
And, as we know, we don't need all of them because, for example,
if $B = B_1 \cup B_2$ and $B_1 \cap B_2 = \varnothing$,
then $\Pr_X(B) = \Pr_X(B_1) + \Pr_X(B_2)$. To put it pedantically, 
we can't define $\Pr_X(B)$ anyway we like. We must make sure
that it is consistent (countable additivity must hold).
\begin{quote}
So the question is: can we throw away some (many) of the values $\Pr(B)$
without losing information?
\end{quote}
The answer is yes. It suffices to
know $\Pr_X(B)$ only for $B$ of  specific form. There are many choices.
One choice is to take 
\[
B=(-\infty , x],
\]
where $x$ ranges from $-\infty$ to $\infty$ and consider only 
(see \fbox{Example 1.5})
\begin{equation}
\label{DF}
F(x) := \Pr_X(-\infty, x], \quad x \in \R.
\end{equation}
So I claim that:
\begin{lemma}
\label{314}
Knowledge of $\Pr_X$ on this class of sets only (semi-infinite
intervals) implies knowledge of $\Pr_X$ on the whole of $\BB$. 
\end{lemma}
This is a big claim. But we shall prove it by construction. 
First, let us see the properties of $F$.
\begin{lemma}
\label{kkk}
(i) $x_1 < x_2 \Rightarrow F(x_1) \le F(x_2)$,
(ii) $\lim_{x\to-\infty} F(x) =0$,
(iii) $\lim_{x\to+\infty} F(x) =1$,
(iv) $\lim_{n \to \infty} F(x+1/n) = F(x)$. 
\end{lemma}
\begin{proof}
(i) If $x_1 < x_2$ we have $(-\infty, x_1] \subset (-\infty, x_2]$
and so $\Pr_X (-\infty, x_1] \le \Pr_X (-\infty, x_2]$.
(ii)\&(iii) Since $F$ is monotonic with values between $0$ and $1$
it has a limit both as $x$ tends to $-\infty$ and $+\infty$.
We have $\cap_{n \in\Z} (-\infty, n] = \varnothing$, so $\Pr_X(-\infty, n]
\to 0$ as $n \to -\infty$. Similarly, $\cup_{n \in \Z} (-\infty,n] = \R$,
so $\Pr_X(-\infty, n] \to \Pr_X(\R)=1$ as $n \to +\infty$.
(iv) $\cap_n(-\infty, x+1/n]= (-\infty, x]$.
\end{proof}

\noindent{\bf Remarks:}\\
1. Notice that $F(x-1/n)$ does NOT necessarily converge to $F(x)$
because $\cup_n(-\infty, x-1/n] = (-\infty, x)$, and so $\lim_{n\to\infty}
F(x-1/n) = \Pr_X(-\infty, x)$ which will be different from $\Pr_X(-\infty, x]$
if $\Pr_X\{x\} > 0$.
\\
2. There is no good reason that we chose this class of sets, other than
people have been using it by convention. For instance, we could have
chosen open semi-infinite interval $(-\infty, x)$, in which case (iv) of
Lemma \ref{kkk} would be replaced by $\lim_{n \to \infty} F(x-1/n) = F(x)$.


\noindent{\bf Proof of Lemma \ref{314}}
Consider the coin-flip $\Omega=\{0,1\}^\N$.
$U(\omega) = \sum_{n=1}^\infty
\frac{\omega_n}{2^n}$. 
Then $U$ is a random variable and
$\Pr$ is, indeed, a probability on $(\Omega, \FF)$,
where $\FF$ is defined through \eqref{FF1} or \eqref{FF2}.
We also showed that $\Pr(U \le u) = u$ for all $u \in [0,1]$.
Suppose now that $F$, as in \eqref{DF}, is given.
Define
\begin{equation}
\label{FI}
F^{-1} (u) := \sup\{x \in \R: ~ F(x) \le u \}.
\end{equation}
By Lemma \ref{balg}, $F^{-1}(U)$ is a random variable. In other words,
$F^{-1} \comp U : (\Omega, \FF) \to (\RR, \BB)$ is measurable.
Suppose that, for some $u, t$, we have $F^{-1}(u) \le t$.
This means that $t$ is an upper bound of the set 
$\{x \in \R: ~ F(x) \le u \}$.
Hence for all $x \in \R$, if $F(x) \le u$ then $ x \le t$.
Equivalently, for all $x \in \R$, if $ x > t$ then $F(x) > u$.
Equivalently, for all $\epsilon > 0$, $F(t+\epsilon) > u$.
Equivalently, for all $n \in \N$, $F(t+1/n) > u$.
Thus,
\[
\{\omega \in \Omega:~ F^{-1}(U(\omega)) \le t\} = 
\{\omega \in \Omega:~ \forall n \in \N ~ F(t+1/n) > U(\omega)\}.
\]
Hence the probabilities of the two sets (notice they both belong
to $\FF$) are the same:
\[
\Pr(F^{-1}(U) \le t) = \Pr (\forall n \in \N ~ F(t+1/n) > U).
\]
By the fact that $\Pr(A_n) \to \Pr(A)$ if $A_n$ is a decreasing sequence
of sets with intersection $A$, we have
\[
\Pr (\forall n \in \N ~ F(t+1/n) > U)
= \lim_{n \to \infty} \Pr(U < F(t+1/n)).
\]
By Lemma \ref{udf}, and the right-continuity of $F$ (Lemma \ref{kkk}),
\[
\lim_{n \to \infty} \Pr(F(t+1/n) > U) = \lim_{n \to \infty} F(t+1/n)
= F(t).
\]
Thus the random variable $F^{-1} \comp U$ has the same law as $X$.
Hence, for all $B \in \BB$, 
\[
\Pr_X(B) = \Pr(F^{-1}(U) \in B)
= \Pr\{\omega\in \{0,1\}^\N:~ F^{-1}(U(\omega)) \in B\}
\]
So, knowledge of $\Pr_X$ on sets of the form $(-\infty, x]$ implies
knowledge of $\Pr_X(B)$ for all $B \in \BB$ by the explicit formula
of the last display.
$\Box$

\begin{definition}
A function $F : \R \to \R$ is called distribution function iff
(i) $x_1 < x_2 \Rightarrow F(x_1) \le F(x_2)$,
(ii) $\lim_{x\to-\infty} F(x) =0$,
(iii) $\lim_{x\to+\infty} F(x) =1$,
(iv) $\lim_{n \to \infty} F(x+1/n) = F(x)$.
\end{definition}

\begin{corollary}
If $F$ is a distribution function then there exists a probability $\Qr$
on $(\R, \BB)$ such that $\Qr(-\infty, x] = F(x)$ for all $x \in \R$.
\end{corollary}
\begin{proof}
Let $\Omega = \{0,1\}^\N$.
Let $\FF$ be as in \eqref{FF1} or \eqref{FF2}.
Let $\Pr$ be the probability on $(\Omega, \FF)$ as in Theorem \ref{ouf}.
Let $U : (\Omega, \FF) \to (\RR, \BB)$ be the random variable
defined by $U(\omega) = \sum_{n=1}^\infty 2^{-n} \omega_n$.
Let $F^{-1}$ be defined by \eqref{FI}. 
Let $X = F^{-1} \comp U$. Then $\Qr = \Pr_X$.
\end{proof}

\begin{lemma}
\label{intervals}
Let $X$ be one real random variable with law $P_X$ and distribution function
$F(x) = \Pr_X(-\infty, x]$, $x \in \R$.
Then (i) $\Pr(X \in (a, b]) = F(b)-F(a)$, (ii) $\Pr(X \in (a,b)) = F(b-)-F(a)$,
(iii) $\Pr(X \in [a, b]) = F(b) - F(a-)$,
(iv) $\Pr(X=a) = F(a)-F(a-)$.
\end{lemma}
\begin{proof}
(i) 
\[
(a, b] = (-\infty , b] - (-\infty, a].
\]
(ii)
\[
(a, b) = \cup_{n \in \N} (a, b-1/n]
\]
(iii)
\[
[a, b] = \cap_{n \in \N} (a+1/n, b].
\]
(iv)
\[
\{a\} = [a, a].
\]
\end{proof}
\begin{exe}
Carefully justify the formulae in the proof of Lemma \ref{intervals}.
\end{exe}

\begin{exe}
There is nothing kosher about choosing $F$ so that it is right continuous.
It is, merely, a convention. Another choice could be $F(x) = \Pr(-\infty, x)$,
which (show this) results into a left continuous function.
Yet another choice is to take this last function and modify it
at each of points of discontinuity $x$ and giving it the value $\tfrac{1}{2}
(F(x-) + F(x+))$.
\end{exe}



\section{Types of distribution functions}
In this section we discuss the various kinds of distribution functions
on $\R$.
\subsection{Discrete distribution functions}
A discrete distribution function is the distribution function of
a discrete random variable $X$ with values in some countable subset $S$ of $\R$.
Assume that $p(s) = \Pr(X = s) > 0$ for all $s \in S$.
Such a distribution function
satisfies $F(s)-F(s-) > 0$ for all $s \in S$.
Indeed, $F(s) - F(s-) = \Pr(X=s)$.
Also, if $(a,b)$ is an open interval containing no points 
of $S$, then $F$ is constant on $(a,b)$. Indeed,
if $a < x < b$ then $F(x)-F(a) = \Pr(a < X \le x) = \sum_{s \in S, a < s \le x}
\Pr(X=s) =0$. 
\begin{example}
Let $X$ be a random variable such that $\Pr(X=n) = 2^{-n}$, $n \in \N$.
Then its distribution function looks like
\begin{center}
\epsfig{file=figs/ddf.eps,width=7cm}
\end{center}
\end{example}
\begin{example}
Let $X$ be a random variable such that for every rational number
of the form $m/n$ where $m, n$ are integers with no common factors,
we have $\Pr(X=m/n) = c 2^{-(m+n)}$ where $c$ is chosen
so that $\Pr(X \in \Q) =1$.
Its distribution function is discrete because $\Q$ is countable.
Unfortunately, I can't draw it. (There are no intervals $(a, b)$ containing
no rational points.)
\end{example}

\subsection{Continuous distribution functions}
A distribution function $F$ is continuous if it is a continuous function,
i.e.\ if $F(x) - F(x-) =0$ for all $x \in \R$.
\begin{example}
Consider the random variable $U$ with $\Pr(U \le u) = u$ for all $u \in [0,1]$.
Such a random variable exists (we constructed it). Its distribution function
looks like
\begin{center}
\epsfig{file=figs/cdf.eps,width=4cm}
\end{center}
\end{example}
Excepting the points $0, 1$ we have that it is also differentiable
with derivative $f(u) = 1$ if $0 < u < 1$ and $0$ otherwise..
If we arbitrarily define $f(0) = f(1) =0$, we also have 
$\int_{-\infty}^u f(t) dt = F(u)$ for all $u \in \R$.
We like such distribution functions:
\subsubsection{Absolutely continuous distribution functions}
A distribution function $F$ is called {\sc absolutely continuous}
if there exists a function $f$ (called {\sc density} of $F$) such that
\[
F(x) = \int_{-\infty}^x f(t) dt, \quad x \in \R.
\]
\footnote{
The integral in the display is a Lebesgue integral. 
For a definition, skip to \S \ref{LI}.
For the time being, you may think of it as the standard Riemann integral
of Integral Calculus.
}
The density is not uniquely defined. For instance, it can be changed
on a finite set and such a change will not affect the integral above.
Usually, one\footnote{
unconsciously}
imposes additional regularity conditions, such as continuity,
resulting in uniqueness.

But not all continuous distribution functions are absolutely continuous:
\subsubsection{Singularly continuous distribution functions}
A distribution function $F$ is called {\sc singularly continuous}
if it is continuous but not absolutely continuous.
We need to show that there are such functions.
\begin{example}
\label{ccc}
Consider the coin-flip space $(\Omega=\{0,1\}^\N, \FF, \Pr)$ and let
\[
V(\omega) := \sum_{n=1}^\infty \frac{2\omega_n}{3^n}.
\]
%In Exercise \ref{ccce} you are asked to show that $V$ has a continuous
%distribution function which is not absolutely continuous. Therefore
%$V$ has no density.
\end{example}
\begin{center}
\epsfig{file=figs/sdf.eps,width=5cm}
\end{center}

\begin{exe}
\label{ccce}
Show that the random variable $V$ defined in Example \ref{ccc} has a continuous
but not absolutely continuous distribution function.
\end{exe}

\subsection{General distribution functions}
Suppose that $F, G$ are distribution functions. Then, for any
$\lambda \in (0,1)$, the function $\lambda F + (1-\lambda G)$ is
a distribution function. (Probabilistically,  if $X, Y$ are random variables
with distribution functions $F, G$, respectively, then we can define
a new random variable $Z$ which equals $X$ with probability $\lambda$
or $Y$ with probability $1-\lambda$.)
So, if $F$ is discrete and $G$ continuous then $\lambda F + (1-\lambda G)$
is neither discrete nor continuous: it is mixed.
The question is: Can we exhaust all distribution functions by taking
mixtures of the three types mentioned above?
The answer is yes:
\begin{theorem}
Let $F$ be a distribution function on $\R$. Then $F$ can be {\em uniquely}
written as 
\[
F= \lambda_d F_d + \lambda_{ac} F_{ac} + \lambda_{sc} F_{sc}
\]
where $F_d, F_{ac}, F_{sc}$ are discrete, absolutely continuous, singularly
continuous distribution functions, respectively, and where the coefficients
are nonnegative such that $\lambda_d + \lambda_{ac} + \lambda_{sc}=1$.
\end{theorem}
The last two terms of this decomposition are known as the
continuous part of $F$. The first two terms are known as the
singular part of $F$. We will not prove this theorem, but refer, e.g.\
to \cite{hs}.

\subsection{Differentiation: a word of caution}
The subject of densities involves the concept of a derivative of
functions that are not necessarily everywhere differentiable. 
Mimicking the definition of a density, we will say that a function $G$
has density $g$ if $G'(x) = g(x)$ for almost all $x$. The latter statement
means that it holds true that $G'(x) = g(x)$ for all $x$ in some set $A$
whose complement is small in the sense that for all $\epsilon > 0$
there exist intervals $I_n$, $n \in \N$ with lengths $\lambda_n$, $n \in \N$,
such that $\sum_n \lambda_n < \epsilon$ and $A^c \subset \cup_n I_n$.
We take this latter statement as a definition:
\begin{definition}
\label{mz}
(i) We say that a set $B \subset \R$ has {\sc measure zero} if
all $\epsilon > 0$
there exist intervals $I_n$, $n \in \N$ with lengths $\lambda_n$, $n \in \N$,
such that $\sum_n \lambda_n < \epsilon$ and $B \subset \cup_n I_n$.
\\
(ii) A function $G : \R \to \R$ is said to be {\sc almost everywhere
differentiable} if $G'(x)$ exists for all $x \in A$ where $A^c$ has
measure zero.
\end{definition}
We can verify the following:
\begin{itemize}
\item
Any countable set has measure zero.
\item
A set $B \subset [0,1]$ has measure zero if and only if a
uniform random variable $U$ in $[0,1]$ satisfies $\Pr(U \in B)=0$.
\item
An absolutely continuous distribution function is almost
everywhere differentiable.
\end{itemize}
What kind of functions $G$ are almost everywhere differentiable with a 
derivative $g$ that can be used to recover the function? That is, for what
kind of functions $G$ can we apply the Fundamental Theorem of Calculus (FTC),
i.e.\ the statement that $G(b)-G(a) = \int_a^b g(x) dx$?
Calculus tells us that if $G$ is piecewise continuously differentiable 
then this is true.
However, we saw, by means of distribution functions, not only
that the FTC holds more generally but it is desirable to understand
it more generally because random variables with not everywhere differentiable
distribution functions abound in theory and in practise.
Here is a definition.
\begin{definition}
A function $G: \R \to \R$ is called {\sc absolutely continuous}
if for all $\epsilon > 0$ there exists a $\delta>0$
such that for any finite collection of disjoint intervals $[a_k, b_k]$
we have $\sum_k|G(b_k)-G(a_k)| < \epsilon$
provided that  the sum of the lengths of the intervals is less than $\delta$.
\end{definition}
\begin{exe}
A differentiable function is absolutely continuous.
An absolutely continuous function is continuous.
\end{exe}
\begin{theorem}
Any absolutely continuous function $G$ is differentiable almost everywhere
and if $g$ is its derivative then the FTC holds.
\end{theorem}
For a proof see \cite{hs}.
Alternatively, one can use Probability Theory to prove all that,
provided that one has understood the theory of Martingales, a subject
of a later chapter. Indeed, much of this generalised differentiation
theory achieves a beautiful interpretation and becomes comprehensible
in probabilistic terms, via Martingale Theory.

\begin{exe}
Show that a continuous and piecewise differentiable function $G$
is almost everywhere differentiable.
\end{exe}



\section{Transformation rules and densities}
Consider a random variable $X : (\Omega, \FF) \to (\RR, \BB)$.
Suppose $\Pr$ is a probability on $(\Omega, \FF)$. We are interested
in the distribution $\Pr_X$ of $X$. Suppose, for some reason, we don't like
it and want to change it to something else. There are two ways to do this.
First, we can change the probability $\Pr$ and replace it by some other
probability $\Qr$. Then $\Pr_X$ will be replaced by $\Qr_X$.
Second, we can take a function $H: (\RR, \BB) \to (\RR, \BB)$
and replace $X$ by $H\comp X$. Then $\Pr_X$ is replaced by 
$\Pr_{H \comp X}$. The two procedures are not, in general, equivalent.

Suppose, for instance, that $X$ is a discrete random variable. Then 
any one-to-one function $H$ will not change the probabilities of
singletons $\{s\}$ such that $\Pr_X\{s\}>0$, but, merely, will
rename them: $\{s\}$ will be transformed to $\{H(s)\}$ and its
probability will remain the same.
Even if $H$ is not one-to-one, there is not much that $H$ can do to
change the probabilities. Consider, for instance, a random variable $X$
with values $1, 2, 3$ and probabilities $p_1, p_2, p_3$, respectively.
Then the most a function $H$ can do is either be one-to-one, in
which case $H(1), H(2), H(3)$ will retain the old probabilities,
or map two points, say $1, 2$, to a single point,
with probability $p_1+p_2$ and leave the the third intact.
Thus, the types of changes in the distribution of 
a discrete $X$ that can be achieved by taking a function 
of it are quite restricted. To really change its distribution {\em ad libitum},
we need to change the underlying probability $\Pr$.

For the case of absolutely continuous random variables, the story is
different: a merely one-to-one function $H$ can simultaneously
change the values and the distribution in a quite general fashion.

\begin{theorem}
\label{denstrans}
Let $X$ be an absolutely continuous random variable in $\R$ with density $f$.
Let $\phi : \R \to \R$ be strictly increasing differentiable function
and let $\psi$ be its inverse function.
Then $\phi(X)$ a random variable with absolutely continuous
distribution function and density
\[
\psi'  \cdot f \comp \psi \text{ on } \phi(\R),
\]
and $0$ elsewhere.
\end{theorem}
\begin{proof}
Since $\phi$ is strictly increasing, its inverse function exists
and has domain $\phi(\R)$. Then, the distribution function
of $\phi(X)$ is, for any $t \in  \phi(\R)$,
\[
\Pr(\phi(X) \le t) = \Pr (X \le \psi(t)) = \int_{-\infty}^{\psi(t)}
f(x) dx.
\]
By changing variable in the integral we have
\[
 \int_{-\infty}^{\psi(t)} f(x) dx
= \int_{-\infty}^t f(\psi(s)) {\psi}'(s) ds,
\]
where we set $\psi'(s) =0$ for $s \not \in \phi(\R)$.
{From} the definition of an absolutely continuous distribution function we see
that, indeed, $\phi(X)$ has absolutely continuous distribution function
and its density is the function inside the last integral.
\end{proof}

\begin{exe}
Let $U$ be a uniform random variable in the interval $(0,1)$. Find the
density function of $e^{e^U}$.
\end{exe}

Theorem \ref{denstrans} assumes that $\phi$ is strictly increasing.
It is immediate to find out the formula for strictly decreasing $\phi$.
Generalising to more general functions is possible and relatively easy
for random variables with values in $\R$ (the story in $\R^d$ is
more complicated). For instance, we may assume that $\phi$ is
piecewise differentiable. The problem becomes a problem in differential
calculus and the general theorem is omitted. However, an example
is due:
\begin{exe}
Let $X$ be a random variable with density $f(x) = c(1+x^2)^{-1}$,
$x \in \R$. Let $\phi(x) = \cosh(x)$. Find the density (and hence
show that it exists) of $\phi(X)$.
\end{exe}


\section{Expectation} 
The expectation of one real random variable is, if it can be defined,
an important numerical aspect of the random variable. It is justified,
for instance, by the Theorem (Law) of Large Numbers which will be
proved at a later chapter.

It is easy to define the expectation of a discrete random variable $X$
with values in $\R$ and probability mass function $p(x)$. Let
$S$ be the set of $x$ such that $p(x) > 0$. Then
\[
\E X   = \sum_{x \in S} x p(x),
\]
provided that this sum can be defined.
We know from Analysis (see \cite{hs}) that the sum of positive numbers
can be defined irrespective of which order we sum the numbers up. However,
not all the summands above are necessarily positive. So let us
consider the positive and negative terms separately and try to define
\[
\E X = \sum_{x \in S_+} x p(x) - \sum_{x \in S_-} (-x) p(x),
\]
where $S_+ := \{ x \in S:~ p(x) > 0\}$, 
where $S_- := \{ x \in S:~ p(x) < 0\}$.
Each of the two sums, separately, is a sum of positive terms, hence it
is well-defined. The only ``problem'' is that such a sum can take 
value $+\infty$. If both sums are finite then $\E X$ is a finite number.
If the first sum is $+\infty$ but the second finite then $\E X =
+\infty$. Similarly, if the first is finite but the second infinite,
then $\E X = -\infty$. The only case where we cannot talk (cannot define)
$\E X$ is when both sums are infinite.

When $X$ has absolutely continuous distribution function with density $f$,
one can define $\E X$ similarly:
\[
\E X = \int_0^{\infty} x f(x) dx - \int_{-\infty}^0 (-x) f(x) dx,
\]
provided that not both integrals are infinity.

In the general case, we need to be more prudent. We will treat the general
case, not only because there are random variables which are neither
discrete or absolutely continuous but because we can seldom (very seldom
indeed) rely on knowledge of the probability mass function or density 
function. 





\subsection{Definition of expectation}
We are going to define the expectation of a random variable 
$X: (\Omega, \FF) \to (\R, \BB)$ with respect to a probability $\Pr$
sitting on $(\Omega, \FF)$. We will use the notation $\E_\Pr X$
or, simply, $\E X$ is the probability $\Pr$ is understood
from the context. After constructing this, we will see
that it does not depend on the choice of probability space,
but only on the law of $X$, namely, we shall show that 
if $X' : (\Omega', \FF') \to (\R, \BB)$ is another random variable
and $\Pr'$ a probability on $(\Omega', \FF')$ such that
$\Pr_X = \Pr'_{X'}$ then $\E_{\Pr} X = \E_{\Pr'} X'$.

\subsubsection{$\rhd$ SIMPLE RANDOM VARIABLES}
The simplest possible random variable is 
\[
\1_A(\omega) = \begin{cases}
1, & \text{ if } \omega \in A,\\
0, & \text{ if } \omega \not \in A
\end{cases}
\]
Since $\1_A$ takes value $1$ with probability $\Pr(A)$ or $0$ with 
the complementary probability, it is only reasonable to define
\[
\E \1_A = \Pr(A).
\]
We ``know'' that the expectation should be linear. So we can extend this
definition to linear combinations of indicators (simple random variable)
and define
\begin{equation}
\label{Es}
\E (a_1 \1_{A_1} + \cdots + a_m \1_{A_m})
= a_1 \Pr(A_1) + \cdots + a_m\Pr(A_m).
\end{equation}
Is this a good definition? There is a slight issue here because 
a simple random variable can be written as linear combination of indicators
in two different ways. For example
\[
8 \1_{A} -3 \1_B = 8 \1_{A \setminus B} -3 \1_{B \setminus A}
+ 5 \1_{AB}.
\]
Using the left side we should define the expectation of it
$8 \Pr(A) -3\Pr(B)$, while, using the right side, as
$8 \Pr(A \setminus B) - 3 \Pr(B \setminus A)+ 5 \Pr(AB)$.
So we must have
\[
8 \Pr(A) -3\Pr(B) = 8 \Pr(A \setminus B) - 3 \Pr(B \setminus A)+ 5 \Pr(AB).
\]
This is true because of additivity of $\Pr$. Indeed, write $\Pr(A) =
\Pr(A\setminus B) + \Pr(AB)$, $\Pr(B) = \Pr(B\setminus A) + \Pr(AB)$,
substitute in the left side, and you obtain the right side.
This argument extends to the general case and so the definition \eqref{Es}
is good.

%Let us restrict to {\em nonnegative} simple random variables. 
%We will use Greek letters $\xi, \eta, \ldots$ to denote simple random 
%variables.
\begin{lemma}[algebraic properties]
\label{alg}
Suppose  $\xi, \eta$ are simple random variables on the same
probability space $(\Omega, \FF, \Pr)$. Then:\\
(i) If $\Pr(A)=0$ then $\E \xi \1_A = 0$.
\\
(ii) $\E (c \xi) = c \E(\xi)$ for all $c \in \R$.
\\
(iii) $\E(\xi+\eta) = \E \xi + \E \eta$.
\\
(iv) If $\Pr(\xi \ge 0)=1$ then $\E \xi \ge 0$.
If $\Pr(\xi \le \eta)=1$ then $\E \xi \le \E \eta$.
\end{lemma}
\begin{proof}
(i) Suppose $A$ is an event in $\FF$ with $\Pr(A)=0$. Then $\E \xi \1_A =0$
because: If $\xi=\sum_k a_k \1_{A_k}$ then $\xi \1_A =
\sum_k a_k \1_{A_k A}$ and so $\E \xi \1_A  = \sum_k a_k \Pr(A A_k)$.
But $\Pr(A A_k) \le \Pr(A) = 0$, for all $k$.
%Suppose next $\Pr(\xi \not = \eta)=0$ and let $A = \{\xi \not = \eta\}$.
%Write $\xi = \xi \1_A + \xi \1_{A^c}$, $\eta = \eta \1_A + \eta \1_{A^c}$.
\\
(ii), (iii), (iv) (Almost) immediate from the definition \eqref{Es}.
\end{proof}

We now concentrate to nonnegative simple random variables. We allow
such a random variable to take value $+\infty$. In other words,
$\xi$ is a nonnegative simple random variable if $\xi=\sum_{i=1}^m
a_i \1_{A_i}$, with $a_i \in \R \cup \{+\infty\}$ for all $i$.
The expectation of such a random variable is defined as before:
$\E \xi= \sum_{i=1}^m a_i \Pr(A_i)$ and the possibility that one of the values
may be equal to $+\infty$ worries us not, for all numbers are nonnegative,
so the worst that can happen is that $\E\xi$ may be $+\infty$.

\begin{lemma}[analytical properties]
\label{anal}
Suppose $\xi, \xi_1, \xi_2, \ldots$, 
$\eta_1, \eta_2, \ldots$ are nonnegative 
simple random variables, and $A \in \FF$.
Then:\\
(i) If $\xi_n$ is an increasing sequence with limit $\1_A$ then
$\E \xi_n$ has limit $\Pr(A)$.\\
(ii) If $\xi_n$ is an increasing sequence with limit $\xi$ then
$\E \xi_n$ has limit $\E \xi$.\\
(iii) If both $\xi_n$, $\eta_n$ are increasing sequences such that
$\lim_n \xi_n(\omega) = \lim_n \eta_n(\omega)$ for all $\omega\in \Omega$, then
$\E \xi_n$, $\E \eta_n$ converge to the same limit.
\end{lemma}
\begin{proof}
(i) Let $\epsilon > 0$. If $\omega \in A$,
then $\xi_n(\omega)$ converges to $1$ and so, for all large $n$,
$\xi_n(\omega) > 1-\epsilon$. In other words,
the sequence of events $\{ \xi_n > 1-\epsilon\}$ 
is increasing with union $A$.
Hence $\Pr(\xi_n > 1-\epsilon)$ increases and has limit $\Pr(A)$. But
\[
\1_A \ge \xi_n \ge (1-\epsilon) \1(\xi_n > 1-\epsilon).
\]
Therefore, by Lemma \ref{alg}(iv),
\[
\Pr(A) \ge \E \xi_n \ge (1-\epsilon) \Pr(\xi_n > 1-\epsilon).
\]
Since the last term converges to $\Pr(A)$ and since $\epsilon$ 
is arbitrary, we have that $\E \xi_n$ converges to $\Pr(A)$.
\\
(ii) Let $a_1, a_2, \ldots, a_m$ be the distinct nonzero 
values of $\xi$. Then $\xi = \sum_{i=1}^m a_i \1(\xi = a_i)$.
Since $\xi_n \uparrow \xi$, we have $\xi_n \1(\xi=a_i) \uparrow \xi\1(\xi=a_i)
=a_1 \1(\xi=a_i)$, and so, $a_i^{-1} \xi_n \1(\xi=a_i) \uparrow \1(\xi=a_i)$.
Applying (i), we have $\E [ a_i^{-1} \xi_n \1(\xi=a_i) ]
\uparrow P(\xi=a_i)$, and so, by Lemma \ref{alg}(ii), 
$\E [\xi_n \1(\xi=a_i) ] \uparrow a_i P(\xi=a_i)$, for all $i=1, \ldots, m$.
Summing over $i$, we have
\[
\sum_{i=1}^m \E [\xi_n \1(\xi=a_i) ] \uparrow \sum_{i=1}^m a_i P(\xi=a_i).
\]
By Lemma \ref{alg}(iii), the left side equals $\E \xi_n$,
while, by the definition \eqref{Es}, the right side equals $\E \xi$.
\\
(iii)
Since both sequences are increasing and have the same limit we have
\[
\lim_{m \to \infty} (\xi_n \wedge \eta_m) = \xi_n,
\quad 
\lim_{n \to \infty} (\xi_n \wedge \eta_m) = \eta_m.
\]
By (ii), we have
\[
\lim_{m \to \infty} \E(\xi_n \wedge \eta_m) = \E \xi_n,
\quad 
\lim_{n \to \infty} \E (\xi_n \wedge \eta_m) = \E \eta_m.
\]
Since the numerical sequence $\E (\xi_n \wedge \eta_m) $ is increasing in
both arguments, we have that the limits over $n$ and over $m$ can be
interchanged and so $\lim_{n \to \infty} \E \xi_n =
\lim_{m \to \infty} \E \eta_m$.
\end{proof}


\subsubsection{$\rhd$ NONNEGATIVE RANDOM VARIABLES}
Suppose that $X$ is a nonnegative random variable that may,
possibly, take value $+\infty$.
We define
\[
\E X:= \sup\{ \E \xi:~ \xi \text{ is simple nonnegative, and } \xi \le X\}.
\]
We immediately have that there exists a sequence $\eta_n$ of simple random
variables such that $\eta_n \le X$ for all $n$ and $\E \eta_n \to \E X$.
\begin{lemma}
\label{EU}
For ANY sequence $\xi_n$ of simple nonnegative random variables such that
$\xi_n \uparrow X$, we have $\E \xi_n \uparrow \E X$.
\end{lemma}
\begin{proof}
As we just pointed out,
there is one sequence $\eta_n$ of nonnegative simple RVs 
such that $\eta_n \le X$ and $\E\eta_n \uparrow \E X$.
Let $\xi_n$ be a sequence 
of simple random nonnegative variables such that $\xi_n \uparrow X$.
Define
$\zeta_n = \max(\eta_1, \ldots, \eta_n, \xi_n)$.
Clearly, $\zeta_n$ is simple, and $\zeta_n \le X$. Also, $\zeta_n$ 
is increasing with limit $X$. 
Since both $\xi_n$ and $\zeta_n$ increase to the same limit,
by Lemma \ref{anal}(iii), $\E \xi_n$ and $\E \zeta_n$ have the same limit.
But $\eta_n \le \zeta_n \le X$. Hence $\E \eta_n \le \E \zeta_n \le \E X$.
Since $\E \eta_n$ has limit $\E X$, we conclude that $\E \zeta_n$ has limit
$\E X$. Therefore $\E \xi_n$ has limit $\E X$ also. 
\end{proof}

In the course of the proof we said that we can find a sequence of simple
functions that increases to $X$. This is done through, for example,
 the functions  $\tau_n$ defined by \eqref{tau}.
\[
\tau_n(x) := 2^{-n} \lceil 2^n x\rceil  \wedge n.
\]
Since
\[
\lceil x\rceil = \sum_{k=1}^\infty \1(k-1 \le x < k), \quad x \ge 0
\]
we can write
\[
\tau_n(x) := \sum_{k=1}^{n 2^n} 2^{-n}  k \1(k-1 \le 2^n x < k), \quad x \ge 0.
\]
Each $\tau_n$ is left-continuous and $\tau_n(x) \to x$ as $n \to \infty$
for each $x$. Moreover, $\tau_n(x) \le \tau_{n+1}(x)$ for all $x$.
Therefore, for any nonnegative RV $X$, we have that $\tau_n(X)$ is an 
increasing sequence of simple nonnegative RVs with $\tau_n(X) \uparrow X$
and, by Lemma \ref{EU}, 
\[
\E X = \lim_{n \to \infty}  \sum_{k=1}^{n 2^n} 
\frac{k}{2^n} \Pr\bigg(\frac{k-1}{2^n} \le X < \frac{k}{2^n}\bigg).
\]

Extending Lemma \ref{EU}, we obtain
\begin{theorem}[monotone convergence theorem]
\label{mct}
For ANY sequence $X_n$ of nonnegative random variables such that
$X_n \uparrow X$, we have $\E X_n \uparrow \E X$.
\end{theorem}
\begin{proof}
By Lemma \ref{EU}, $\E X = \lim_{m \to \infty} \E \tau_m(X)$. By
the left-continuity of $\tau_m$, we have $\tau_m(X_n) \uparrow \tau_m(X)$,
as $n \to \infty$, and by Lemma \ref{EU}, the same is true after taking  
expectations. So:
\[
\E X = \lim_{m \to \infty} \lim_{n \to \infty} \E \tau_m(X_n).
\]
Because the numerical sequence $\E \tau_m(X_n)$ is increasing in both
indices $m$ and $n$, we can interchange the limits:
\[
\E X = \lim_{n \to \infty} \lim_{m \to \infty} \E \tau_m(X_n)
= \lim_{n \to \infty} \E X_n,
\]
where the last equality follows, again, from Lemma \ref{EU}. 
\end{proof}

\begin{lemma}
\label{yyy}
Let $X, Y$ be nonnegative random variables on $(\Omega, \FF, \Pr)$. Then:
\\
(i) $\E X = 0$ if and only if $\Pr (X>0)=0$.
\\
(ii) $\E (c X) = c \E X$ for all $c \ge 0$.
\\
(iii) $\E(X+Y) = \E X + \E Y$.
\\
(iv) 
If $\Pr(X \le Y)=1$ then $\E X \le \E Y$.
\end{lemma}
\begin{proof}
We only prove half of (i). The rest are easy. We have $\{X > 0\}$ is the limit
of $\{X > 1/n\}$, as $n \to \infty$. Hence $P(X>0) = \lim_{n \to \infty}
P(X > 1/n)$. If $P(X>0) > 0$ then $P(X > 1/n) > 0$ for some $n$ and,
since $X \ge (1/n) \1(X>1/n)$ we have $\E X \ge (1/n) \Pr(X>1/n)$,
i.e.\ $\E X > 0$.
\end{proof}

\begin{lemma}[Fatou's lemma]
\label{fatou}
For any sequence $X_n$ of nonnegative random variables, $\E \liminf X_n
\le \liminf \E X_n$.
\end{lemma}
\begin{proof}
We have
\[
\inf_{k \ge n} X_k \le X_\ell, \quad \ell \ge n.
\]
So, by (iv) of Lemma \ref{yyy},
\[
\E \inf_{k \ge n} X_k \le \E X_\ell, \quad \ell \ge n,
\]
and so
\[
\E \inf_{k \ge n} X_k \le \inf_{\ell \ge n} \E X_\ell.
\]
Both sides are increasing numerical sequences  in $n$.
The right side increases to $\liminf \E X_\ell$.
The left side increases, by Theorem \ref{mct}, to
$\E \liminf X_n$.
\end{proof}


\subsubsection{$\rhd$ GENERAL RANDOM VARIABLES}
Suppose now $X$ is a random variable with values in $\R$. We say
that $X$ has an expectation if not both $X^+ = \max(X,0)$
and $X^-:=-(-X)^+$ have infinite expectations. In this case,
we define
\[
\E X = \E X^+ - \E X^-.
\]
The definition is, of course, well-motivated: for any number $x$, we have
$x = x^+ - x^-$.

\begin{exe}
If $x$ is a real number, we let, as usual, $x^+ := \max(x,0)$,
$x^-:= -(-x)^+$.
Show that $x^- = -\min(x,0)$ and derive the identities
\[
x = x^+-x^-,
\quad
|x| = x^++x^-,
\quad
\min(|x|, |y|) = \tfrac{1}{2}(|x|+|y|-|x-y|).
\]
Show also that if $a < b$ then $(x \vee a) \wedge b = (x \wedge b) \vee a$.
\end{exe}

We say that $X$ is integrable (with respect to $\Pr$) if
both $\E X^+$ and $\E X^-$ are finite or, equivalently,
if $\E |X| < \infty$. (The latter follows from the identity
$|x| = x^+ + x^-$.)

\begin{lemma}
Let $X, Y$ be integrable random variables on $(\Omega, \FF, \Pr)$. Then:
\\
(i) $\E (c X) = c \E X$ for all $c \in \R$.
\\
(iii) $\E(X+Y) = \E X + \E Y$.
\\
(iv)
If $\Pr(X \le Y)=1$ then $\E X \le \E Y$.
\end{lemma}

If $A \in \FF$ we can define the expectation of $X$ on $A$ by:
\[
\E (X; A) := \E(X \1_A).
\]
If $\Pr(A) > 0$ we can define the expectation of $X$ given $A$ by:
\[
\E(X | A) := \frac{\E(X; A)}{\Pr(A)}.
\]
We remark that $\E(X|A)$ is expectation with respect to the restriction
$\Pr_A$ of $\Pr$ on $A$, i.e.\ with respect to the probability 
\[
\Pr_A : \FF \to \R; \qquad \Pr_A(B) := \Pr(AB), \quad B \in \FF.
\]
In other words,
\[
\E(X | A) = \E_{\Pr_A} X.
\]

\begin{exe}
Show that $|\E X| \le \E |X|$ (whenever $\E X$ is defined).
\end{exe}

\begin{theorem}[Dominated Convergence Theorem]
\label{dct}
Let $X_n$ be a sequence of random variables such that 
$X(\omega) = \lim_{n \to \infty} X_n(\omega)$ exists and
such that $|X_n(\omega)| \le Y(\omega)$ for all $n$ and $\omega$,
and $\E |Y| < \infty$.
Then $\E|X_n-X|$ converges to zero.
\end{theorem}
\begin{proof}
Apply Fatou's lemma \ref{fatou} to $2Y-|X_n-X|$.
\end{proof}



\subsection{Substitution rule} % and chain rules}
\begin{lemma}
\label{subst}
Consider the measurable functions
\[
(\Omega, \FF) \xrightarrow[]{Z} (S, \SS) \xrightarrow[]{H} (\R, \BB).
\]
Let $\Pr$ be a probability on $(\Omega, \FF)$. Let $\Pr_Z$ be the law
of $Z$.
Then
\[
\E_{\Pr} H \comp Z = \E_{\Pr_Z} H,
\]
whenever wither side exists.
(Here, $H \comp Z$ is one real random variable on the
probability space $(\Omega, \FF, \Pr)$ and
$H$ is one real random variable on the probability space $(S, \SS, \Pr_Z)$.)
\end{lemma}
\begin{proof}
Suppose $H$ is an indicator random variable, i.e.\ $H = \1_B$ for
some $B \in \SS$. Then $\E_{\Pr_Z} \1_A = \Pr_Z(A)$ by the definition
of the expectation of a simple random variable. On the other hand,
$H \comp Z = \1_A(Z)$ is an indicator random variable on $(\Omega, \FF)$: it
is the indicator of the set $\{\omega \in \Omega:~ Z(\omega) \in A\}$.
Hence, again by the by the definition
of the expectation of a simple random variable,
$\E_{\Pr} H \comp Z = \Pr(Z \in A)$.
But $\Pr_Z(A) = \Pr(Z \in A)$ by the definition of the law
of the random variable $Z$ (see section \ref{law}).
Suppose next that $H$ is a simple random variable. Use the above and
linearity of expectation to get the result.
Suppose that $H$ is a nonnegative random variable.
Use Lemma \ref{mct}.
Finally, suppose that $H$ has no sign restriction, and use the
definition of expectation.
\end{proof}

\begin{corollary}
\label{iii}
If $X$ is a real random variable on $(\Omega, \FF, \Pr)$ with expectation
$\E_{\Pr} X$ and law $\Pr_X$ then
\[
\E_{\Pr} X = \E_{\Pr_X}\iota
\]
where $\iota: \R \to \R$ is the identity function: $\iota(x) \equiv x$.
\end{corollary}
Therefore, the expectation of a random variable depends only on its law.

Suppose that $X$ is a discrete random variable with values in
a finite set $S \subset \R$ and probability mass
function $p(x), x \in S$.
Since $X = \sum_{x \in S} x \1(X=x)$ is a simple random variable, 
we immediately have that $\E X = \sum_{x \in S} x \Pr(X=x) = \sum_{x \in S}
x p(x)$, as needed.
The same formula holds for a discrete random variable with values
in a countable set $S$: Simply enumerate the elements of $S$
and use monotone convergence theorem.

Let us now consider an absolutely continuous random variable $X$
with density $f$. We would like to show that $\E X$ is compatible with
the definition given at the beginning of the section, namely that it
equals $\int_\R x f(x) dx$. To do this, we need to revisit the
notion of an integral:

\subsection{Expectation and densities}
\label{LI}
Let $h: (\R, \BB) \to (\R, \BB)$ be measurable and suppose $h \ge 0$.
Consider the random variable $U$ on the coin-flip space
$(\Omega=\{0,1\}^\N, \FF, \Pr)$, defined by  \eqref{U}.
We define $\int_\R h(x) dx$ by
\[
\int_\R h(x) dx := \sum_{n \in \Z} \E h(U+n).
\]
This is called the Lebesgue integral of $h$.
We also define $\int_a^b h(x) dx$ by
\[
\int_a^b h(x) dx := \int_\R h(x) \1(a \le x \le b) dx,
\]
and, more generally, for any $B \in \BB$,
\[
\int_B h(x) dx := \int_\R h(x) \1(x \in B) dx.
\]
If $h$ has no restriction on sign, we define $\int_a^b h(x) dx$
as $\int_a^b h^+(x) dx - \int_a^b h^-(x) dx$ 
provided that not both terms are infinite.
This integral behaves like the ordinary Riemann integral for ``nice''
functions (e.g.\ for continuous or piecewise continuous functions).

More generally, if $F: \R \to \R$ is an increasing function, we define
\[
\int_\R h(x) F(dx) = \int_\R h(F^{-1}(x)) dx, 
\]
where $F^{-1}(x) := \inf \{t \in \R:~ F(t) > x\}$.
This is the Lebesgue-Stieltjes integral.
It is also denoted by $\int_\R h(x) dF(x)$ or simply as $\int_\R h dF$
when the variable of integration needs no mentioning.

\begin{quote}
\bf
The following theorem connects what one learns in basic Calculus
with what we just defined.
You absolutely need this theorem in order to make the connection
between the standard Calculus tricks and recipes\footnote{
I mean things like $\int_0^x t^2 e^t dt = x^2 e^x - 2 \int_0^x t e^t dt
= (x^2-2x+2) e^x -2$.
}
and what we are talking about here.
\end{quote}
\begin{theorem}
\label{RL}
(i) If $h$ is Riemann integrable on $[a, b]$ then the Lebesgue
integral $\int_a^b h(x) dx$ exists and coincides with the Riemann integral.
\\
(ii) If $h$ is bounded and measurable then it is Riemann integrable on $[a,b]$
if the set of discontinuities of $h$ have measure zero, in the sense
of Definition \ref{mz}.
\end{theorem}

\begin{example}
For example, if $h$ is piecewise continuous, then its discontinuities
have measure zero and so it is Riemann integrable.
\end{example}

\begin{example}
As a counterexample, consider the function $h(x) = \1(x \in \Q)$,
$0 \le x \le 1$. This function is discontinuous on every
point of $[0,1]$. The interval $[0,1]$ does not have measure zero.
Hence it is not Riemann integrable. However, $h$ is measurable and nonnegative,
and so it does have a Lebesgue integral: this integral equals $\E h(U)
= \Pr(U\in \Q) = 0$.
\end{example}

%\no{\bf Proof of Theorem \ref{RL} [sketch]:}
%\qed

Theorem \ref{RL} enables us to use all rules we learn in basic Integration
Calculus to the case of Lebesgue integration when the two integrals
coincide.


Suppose now that $X$ is a random variable with absolutely continuous
distribution function $F$ and density $f$. 
Consider the function $\Qr : \BB \to \R$ defined by 
\[
\Qr(B) := \int_B f(x) dx.
\]
Since $\Qr(B)= \Pr_X(B)$ for $B = (-\infty, x]$, we have
that $\Qr=\Pr_X$.
More generally,
\begin{lemma}
\label{chainrule}
Let $\Pr_X$ be the law of a random variable $X$ with density $f$.
Then, for any measurable $g : (\R, \BB) \to (\R, \BB)$,
\[
\int_\R g(x) f(x) dx = \E_{\Pr_X} g
\]
provided that wither side exists.
\end{lemma}
\begin{proof} 
If $g = \1_B$, then this is what was discussed before the Lemma.
For $g$ simple, we use linearity. For general $g$ we approximate.
\end{proof}

\begin{corollary}
Let $\Pr_X$ be the law of an integrable random variable $X$ with density $f$.
\\
(i) If $\iota$ is the identity function on $\R$ then
\[
\int_\R x f(x) dx = E_{\Pr_X} \iota.
\]
(ii) 
\[
\E X = \int_\R x f(x) dx.
\]
\end{corollary}
\begin{proof}
(i) follows from Lemma \ref{chainrule} with $g = \iota$.
(ii) follows from corollary \ref{iii}
\end{proof}




\begin{exe}
Suppose that $Z$ is a real random variable with absolutely continuous
distribution function and density $f_Z$. Let $H: (\R, \BB) \to (\R, \BB)$
be a measurable function. Suppose that the random variable $X=H(Z)$ has
density $f_X$. Show that the expectation of $X$ (if it exists)
can be computed in two ways:
\[
\E X = \int_\R x f_X(x) dx = \int_\R H(z) f_Z(z) dz.
\]
\end{exe}

\begin{exe}
Let $B \in \BB$ and let $\lambda(B) := \int_\R \1_B(x) dx$ (Lebesgue integral). Show that $\lambda : \BB \to \R$ satisfies
$\lambda(\cup_n A_n) = \sum_n \lambda (A_n)$ whenever the $A_n$ are mutually
disjoint elements of $\BB$ and that $\lambda(A+t) = \lambda(A)$ for all $A \in \BB$, $t \in \R$, where $A+t :=\{a+t:~ a \in A\}$.
The function $\lambda$ is called {\sc length}.
\end{exe}

\begin{exe}
Consider a compass with a laser pointer attached at both ends of the needle.
Suppose there is an infinite screen at some
distance from the compass.
Give it a spin and see mark $X$ the location of the light with respect to
a fixed point O on the screen (positive if it is to the right of O; negative
if it is to the left). Show that $\E X$ is not defined.
(You first must translate this problem in Mathematics.)
\end{exe}

\begin{exe}
Consider the function $F(x):= \sum_{k \in \N} \1(x \le k)$, $x \ge 0$,
$F(x) =0$, $x < 0$.
Show that
\[
\int_\R h(x) F(dx) = \sum_{k=1}^\infty h(k),
\]
whenever the sum on the right makes sense.
\end{exe}





\section{Inequalities}
Mathematics needs inequalities probably more than equalities. Probability,
in particular, which, in some sense, contains a lot of approximation 
ideas needs inequalities. This section discusses some basic ones.

\subsection{Markov, Chebyshev, Chernoff}
\begin{lemma}[Markov inequality]
If $X$ is a nonnegative random variable then
\[
\Pr(X \ge t) \le \frac{\E X}{t}, \quad t > 0.
\]
\end{lemma}
\begin{proof}
We have
\[
t \1(X \ge t) \le X
\]
and $\E$ is preserved by $\le$.
\end{proof}

\begin{definition}
The variance of a real random variable $X$ with $\E X^2 < \infty$ is
defined by
\[
\var X := \E (X- \E X)^2.
\]
\end{definition}

\begin{lemma}[Chebyshev inequality]
If $X$ is a real random variable with $\E X^2 < \infty$
then
\[
\Pr(|X - \E X| \ge t) \le \frac{\var X}{t}
\]
\end{lemma}
\begin{proof}
Apply the Markov inequality to $|X - \E X|$.
\end{proof}

\begin{lemma}[Chernoff inequality]
If $X$ is a real random variable then
\[
\Pr(X \ge t) \le \frac{\E g(X)}{g(t)}
\]
where $g$ is a positive increasing function.
\end{lemma}
\begin{proof}
Since $g$ is increasing,
\[
\{X \ge t\} \subset \{g(X) \ge g(t)\}
\]
Now apply the Markov inequality to $g(X)$.
\end{proof}

\begin{exe}
Let $X$ be a discrete random variable with $\Pr (X=k) = \binom{n}{k} 2^{-k}$,
$k=0,1, \ldots,n$. Estimate $\Pr(X > na)$ for $a>0.5$ using the
above inequalities.
\end{exe}



\subsection{Jensen}
A function $\phi: \R \to \R$ is convex if
\[
\varphi(p a + (1-p) b) \le p \varphi(a) + (1-p) \varphi(b)
\]
for all $a, b \in \R$ and all $0 \le p \le 1$.
Notice that if $\xi$ is a random variable with $\Pr(\xi=a)=p$, $\Pr(\xi=b)=1-p$,
this definition can be written as
\[
\phi(\E \xi) \le \E \phi(\xi).
\]
Jensen's inequality generalises this observation:
\begin{lemma}
\label{jensen}
Let $X$ be a real integrable random variable and $\phi$ a convex function. Then
\[
\phi(\E X) \le \E \phi(X).
\] 
\end{lemma}
Geometrically, a convex function is such that the graph of
the function on the interval $[a, b]$ lies below the straight segment
with endpoints $(a, \phi(a))$, $(b, \phi(b))$.
\begin{center}
\epsfig{file=figs/convex.eps,width=6cm}
\end{center}
If we take a straight line with slope equal to the slope
of this segment and move it down, at some point it will be entirely
below the whole graph of $\phi$. Moreover, if we consider the set
of all straight lines that are below the graph of $\phi$ and take
their envelope (the maximum) then this equals $\phi$.
Namely, 
\begin{equation}
\label{hb}
\phi(x) = \max_{\ell \in L(\phi)} \ell(x), \quad x \in \R,
\end{equation}
where $L(\phi)$ is the collection of all functions 
$\ell(x) \equiv \alpha x+\beta$ such that $\ell \le \phi$.
To show this rigorously, observe that 
\[
a < b < c \Rightarrow
\frac{\phi(b)-\phi(a)}{b-a}
\le
\frac{\phi(c)-\phi(b)}{c-b},
\]
by the definition of convexity.
Let $\epsilon> 0$,  $a=b-\epsilon$, $c=b+\epsilon$
and so
\[
D_-\phi(b) := \lim_{\epsilon \downarrow 0}\frac{\phi(b)-\phi(b-\epsilon)}{\epsilon}
\le
\lim_{\epsilon \downarrow 0}\frac{\phi(b+\epsilon)-\phi(b)}{\epsilon}:= D_+\phi(b),
\]
where the limits exist by monotonicity.
Let $\alpha$ be between $D_-\phi(b)$ and $D_+\phi(b)$. Then, if $x > b+\epsilon$,
we have
\[
\frac{\phi(b+\epsilon)-\phi(b)}{\epsilon}
\le 
\frac{\phi(x)-\phi(b)}{x-b},
\]
and so
\[
\alpha \le D_+\phi(b) \le \frac{\phi(x)-\phi(b)}{x-b}, \quad x > b,
\]
or $\alpha(x-b) + \phi(b) \le \phi(x)$, for all $x \ge b$. Arguing similarly 
for all $x \le b$, we have
\[
\alpha(x-b) + \phi(b) \le \phi(x), \quad x \in \R.
\]
Thus, the function $\ell(x) := \alpha(x-b) + \phi(b) \le \phi(x)$ belongs
to $L(\phi)$ and also, $\ell(b) = \phi(b)$.
This proves \eqref{hb}.

\noindent{\bf Proof of Lemma \ref{jensen}:}
\[ 
\phi(\E X) = \max_{\ell \in L(\phi)} \ell(\E X)
=
\max_{\ell \in L(\phi)} \E \ell(X)
\le
\E \max_{\ell \in L(\phi)} \ell(X)
=
\E \phi(X).
\]
The first equality is due to \eqref{hb}.
The second uses linearity of expectation.
The third uses monotonicity of expectation.
The last reuses \eqref{hb}.
$\Box$

\begin{exe}
Let $a_1, \ldots, a_n$ be positive real numbers. Define
their arithmetic, geometric and harmonic mean
by
\[
A_n=\frac{a_1+\cdots+a_n}{n},
\quad
G_n=(a_1\cdots a_n)^{1/n},
\quad
H_n = \frac{n}{a_1^{-1} + \cdots + a_n^{-1}},
\]
respectively, and show that $A_n \ge G_n \ge H_n$.
\end{exe}



\section{Moments}
\begin{definition}
When $r > 0$, the {\sc $r$-moment} of a nonnegative RV $X$ is defined as 
the quantity $\E X^r$.
The $r$-norm of a real RV $X$ is defined as $ ||X||_r:=(\E |X|^r)^{1/r}$.
\end{definition}

\begin{lemma}
\label{inorm}
The $r$-norm of $X$ is increasing in $r$.
\end{lemma}
\begin{proof}
Let $r < s$ and $\phi(x) = x^{s/r}$, $x > 0$. Notice that $\phi$
is convex. (This follows from the fact that its second derivative is positive.)
Now apply the Jensen inequality.
\end{proof}

\begin{corollary}
If $\E |X|^p < \infty$ for some $p > 0$ then $\E |X|^r < \infty$ for
all $0 < r < p$.
\end{corollary}




\section{H\"older, Minkowski and Cauchy-Bunyakowskii-Schwarz}

\begin{definition}
If $X, Y$ are real random variables on the same $(\Omega, \FF, \Pr)$,
the quantity $\E(X Y)$ (whenever it is defined) is called {\sc correlation}
between $X$ and $Y$. 
The quantity $\cov(X,Y):= \E((X-\E X) (Y-\E Y))$ is called {\sc covariance}
between $X$ and $Y$.
\end{definition}

\begin{lemma}[H\"older inequality]
Let $X, Y$ be real random variables. Then
\[
|\E(XY)| \le ||X||_p ||Y||_q,
\]
for any $p, q > 0$, $p^{-1} + q^{-1} =1$, as long as all 
terms involved exist and are finite.
\end{lemma}
\begin{proof}
Let $(\Omega, \FF, \Pr)$ be a probability space on which
both $X, Y$ are defined. Without loss of generality
assume that they are both nonnegative. Let $q > 1$ and assume that
$\E (Y^q) < \infty$. Consider the probability
\[
\Pr_q(A) := \frac{\E(Y^q \1_A)}{\E(Y^q)}, \quad A \in \FF.
\]
Let $\E_q$ denote expectation with respect to $\Pr_q$.
Therefore, for any nonnegative random variable $W:(\Omega, \FF) \to (\R, \BB)$,
\begin{equation}
\label{WWW}
\E_q W = \frac{\E(Y^q W)}{\E (Y^q)}.
\end{equation}
Letting, in \eqref{WWW}, $W = XY^{1-q}$, we obtain
\[
\E(XY) = \E(Y^q)~ \E_q(XY^{1-q}).
\]
Let $p$ be defined from $p^{-1} + q^{-1} =1$. Necessarily, $p > 1$.
{From} Lemma \ref{inorm} we have
\[
\E_q Z \le (\E_q Z^p)^{1/p},
\]
for any nonnegative
random variable $Z :(\Omega, \FF) \to (\R, \BB)$ with 
$\E Z^p < \infty$.
Therefore,
\begin{align*}
\E(XY) &\le \E(Y^q) ~ (\E_q ((XY^{1-q})^p))^{1/p}
\\
&= \E(Y^q) ~ \left(\frac{\E (X^p Y^q Y^{(1-q)p})}{\E (Y^q)}\right)^{1/p}
\\
&= (\E(Y^q))^{1-1/p} ~ (\E (X^p Y^{q+(1-q)p}))^{1/p}.
\end{align*}
Since $1-1/p = 1/q$ and $q+(1-q)p=0$, the result follows.
\end{proof}



\begin{corollary}{\bf(Cauchy-Bunyakowskii-Schwarz)}
Let $X, Y$ be real random variables. Then
\[
|\E(XY)| \le ||X||_2 ||Y||_2,
\]
as long as all
terms involved exist and are finite.
\end{corollary}
\begin{proof}
Notice that $\tfrac{1}{2}+\tfrac{1}{2}=1$ and apply H\"older.
\end{proof}

\begin{corollary}Let $X, Y$ be real random variables. Let 
\[
\rho(X, Y) := \cov(X,Y) /\sqrt{\var(X)} \sqrt{\var(Y)},
\]
whenever the terms exist.
Then
\[
-1 \le \rho(X,Y) \le 1.
\]
\end{corollary}




\begin{lemma}[Minkowski inequality]
Let $X, Y$ be real random variables. Then
\[
||X+Y ||_p \le ||X||_p + ||Y||_p,
\]
for any $p > 1$, as long as all
terms involved exist and are finite.
\end{lemma}
\begin{proof}
Use the H\"older inequality as follows:
\begin{align*}
\E(|X+Y|^p)
& = \E(|X|~|X+Y|^{p-1}) + \E(|Y|~|X+Y|^{p-1})
\\
&\le [\E(|X|^p)]^{1/p} ~ [\E(|X+Y|^{(p-1)q})]^{1/q}
+[\E(|Y|^p)]^{1/p} ~ [\E(|X+Y|^{(p-1)q})]^{1/q}
\\
&= (||X||_p + ||Y||_p) ~ [\E(|X+Y|^p)]^{1/q},
\end{align*}
\end{proof}



\section{Moment generating functions}
Let $X$ be a real random variable. Since, for any $\theta \in \R$,
the random variable $e^{\theta X}$ is nonnegative, its expectation
exists (but may be equal to $+\infty$). We define the function
$M : \R \to \R\cup\{+\infty\}$ by
\[
M(\theta) := \E(e^{\theta X}), \quad \theta \in \R.
\]
Notice that $M(0) =1$.
This function is useful if $M(\theta) < \infty$ for some $\theta \not = 0$.
(Indeed, there are cases where $\theta=0$ is the only point at which
$M$ is finite.)
If $X$ is a positive random variable, then $M(\theta) < \infty$ for all 
$\theta \le 0$.
If $X$ is a negative random variable, then $M(\theta) < \infty$ for all 
$\theta \ge 0$.
$M$ depends only on the law of $X$. Indeed, using the Substitution Rule
(Lemma \ref{subst}) we can write
\[
M(\theta) = \E_{\Pr_X} (e^{\theta \iota}),
\quad
\text{where } \iota(x) \equiv x,
\]
and, if $X$ has absolutely continuous distribution function $F$ with density
$f$, we can write
\[
M(\theta) = \int_{\R} e^{\theta x} f(x) dx \quad \text{ (Lebesgue integral) }.
\]
The function $M$ is called {\sc moment generating function} because
of the following:
\begin{lemma}
\label{mmm}
Suppose there exist $a < 0 < b$ such that $M(\theta) < \infty$ for
all $a < \theta < b$. Then 
\\
(i) the $r$-moment of $X$ exists for all $r \in \N$
and is given by the $r$-derivative of $M$ at $0$:
\[
\E(X^r) = D^r M(0).
\]
(ii) 
\[
M(\theta) = \sum_{r=0}^\infty \frac{\E(X^r)}{r!} \theta^r,
\quad a < \theta < b.
\]
(iii) There is only one distribution function $F$ such that
if $X$ has distribution function $F$ then it has moment generating function 
$M$.
\end{lemma}
\begin{proof} [sketch]
Using the Dominated Convergence Theorem \ref{dct}, we can see that $M$ is
infinitely differentiable at $0$ with $r$-derivative equal to the
$r$-moment of $X$. Moreover, we can see that $M$ is a real
analytic function around $0$. Hence Taylor's theorem holds,
which yields the second claim.
\end{proof}
%To talk intelligently about moment generating functions we must
%talk about Laplace and Fourier transforms.
 




\newpage

%%% BEGIN APPENDIX %%%%
{\small

\hrule
\begin{center}
{\tiny $\rhd$ }
{\footnotesize $\rhd$ }
{\small $\rhd$ }
{ $\rhd$ }
{\large $\rhd$ }
~APPENDICES~
{\large $\lhd$ }
{ $\lhd$ }
{\small $\lhd$ }
{\footnotesize $\lhd$ }
{\tiny $\lhd$ }
\end{center}
\hrule


\section{APPENDIX A: Sets}

The logic of events plays a much more fundamental r\^ole in
the whole subject than the layman could imagine.
We review basic concepts here.\footnote{
There are no numbers in this section; only sets.
(Of course, numbers are sets; so the above
declaration is offered with apologies to set theorists.)
}

\paragraph{\S}
We express the statement that $x$ is an element of (or belongs to)
a set $A$ by $x \in A$. The negation of the latter is denoted by 
$x \not \in A$.
We write $A \subset B$ for to express
the statement ``$x \in  A \Rightarrow x \in B$''.
We let $A \cap B$ be the intersection
and $A \cup B$ the union of $A$ and $B$. To save space, we often write
$AB$ in lieu of $A \cap B$ and $ABC$ in lieu of $A \cap B \cap C$.
The set $A^c$ is defined through: $``x \in A^c \iff x \not \in A$''.
Na\"ive set theory and first order logic are algebraically equivalent
through the above and through: 
``$A \cap B \iff x \in A \text{ and } x \in B$'',
``$A \cup B \iff x \in A \text{ or } x \in B$''.
We let $B \setminus A = B \cap A^c$
and we write $B-A$ for $B \setminus A$ if $A \subset B$.
The symmetric difference (`exclusive or') $A \xor B$ is defined
as the set of elements of $A$ or $B$ which do not belong to both, i.e.\
$A \xor B = (A \setminus B) \cup (B \setminus A) = (A \cup B) - (A \cap B)$.
If $\{A_j, j \in J\}$ is a collection of sets we let $\cap_{j \in J} A_j$ 
be their
intersection and $\cup_{j \in J} A_j$ their union. Here, $J$ is an 
arbitrary set. If $J=\N$ we write
$\cap_{j \in \N} A_j = \cup_{j=1}^\infty A_j$, and, as usually in Mathematics,
the convention is that the symbol $\infty$ appearing on top is not part
of the index set ($\infty$ is not a natural number).\footnote{ 
Compare this with a sum of real numbers: $\sum_{j=1}^\infty x_j$
means that $j$ runs over $1,2,3\ldots$ but does not take the value $\infty$.
}
%We have $B \setminus \cap_j A_j = \cup_j (B\setminus A_j)$.
Here is an example of how we translate elementary logic (i.e.\ ordinary 
language, say English) in Mathematics: 
\def\sfS{\text{\sf S}}
\def\sfR{\text{\sf R}}
Consider the sentence 
\[
\sfS  =\text{[after some day it will never rain again in Glasgow]}.
\]
If we let 
\[
\sfR_i = \text{[it rains on the $i$-th day in Glasgow]}
\]
we can write $\sfS$ as
\[
\sfS = \text{[$\exists i ~\forall j ~\ge i \text{ not} \sfR_i$]}.
\]
Taking the negation of this sentence\footnote{
To which, I think, we can
safely assign the truth value
}
we get:
\[
\text{not}\sfS = \text{$\text{not}[\exists i ~\forall j ~\ge i \text{ not} R_i]
= [\forall i~ \exists j \ge i ~ R_i]$}.
\]
Translating this back into English, it reads:
\[
\text{not}\sfS = 
\text{[for all days there will be a day in the future during  which 
it rains in Glasgow]}
\]
and, since this is not too palatable even for the literati, we can express
it, equivalently, as
\[
\text{not}\sfS = \text{[it rains in Glasgow infinitely often]}.
\]
What does this have to do with sets? Well, imagine there is a big set (the
``universe'')--call it $\Omega$--containing all possible states of Glasgow at
all days. At the minimum, we want to know whether it rains or not
on each day. So we decide to let an element of $\Omega$ be the sequence
$(\omega_1, \omega_2, \ldots)$ of states of Glasgow, where $\omega_i$
takes values ``rain'' or ``doesntrain'' and represents what happens
on the $i$-th day in Glasgow. So $\Omega$ is the set of all these
sequences, mathematically written as $\Omega = \{\text{rain},
\text{doesntrain}\}^\N$. Then $R_i$ can be taken to be the set of
all sequences $\omega \in \Omega$ such that $\omega_i=\text{rain}$.
You can then check that the set (subset of $\Omega$)
$S = \cup_i \cap_{j \ge i} R_i^c$ corresponds to the statement {\sf S},
while
$S^c = \cap_i \cup_{j \ge i} R_i$ corresponds to the statement not{\sf S}.
In this sense, the so-called Kolmogorov model of Probability merely puts
within a mathematical framework (that of Set Theory)
what we intuitively feel as assigning numbers representing chance to 
statements, to events, to situations describable by ordinary language.
So Probability Theory is ordinary logic together with numbers
assigned to statements. We talk about logic in this Appendix
and about numbers in the next.
%In the language of Set Theory this is called Measure Theory.

\paragraph{\S}
If $A$ is a set then $2^A$ is the set of its subsets.
A set of sets (or ``collection'' of sets) is a subset of $2^A$.
If $A$ has $n$ elements then $2^A$ has $2^n$ elements. 
If $\N$ is the set of natural numbers then $2^\N$ has as many elements
as the set of real numbers.
(And why, on earth, should we use the symbol $2^A$? To explain, consider
a simple set, say $A=\{x,y,z\}$. I can form a subset of $A$ by putting
a $1$ to each element I pick or $0$ to each element I do not pick.
For instance, $011$ means ``do not pick $x$, pick $y$, pick $z$'', i.e.\
it refers to the subset $\{y,z\}$. We thus see there is a correspondence
between subsets of $A$ and triples of $0$'s and $1$'s. How many such triples
do we have? Obviously, $2 \times 2 \times 2 = 2^3$. This explains why
we have $2^3=8$ subsets. If $A$ had $n$ elements, you see there are $2^n$
subsets and so the notation $2^A$ is suggestive of this, and we carry it on
even to cases where $A$ has infinite number of elements.)
\paragraph{\S}
If $f:X \to Y$ is a function then, for any $B \subset Y$ we define
$f^{-1}(B) = \{x \in X: f(x) \in B\}$, and for any $A \subset X$ we define
$f(A) = \{f(x): x \in A\}$.
Thus $f$ can be lifted as a map from $2^X$ into $2^Y$ and we also have
a map $f^{-1}$ from $2^Y$ into $2^X$. We always have
$f (f^{-1}(B)) \subset B$ and $f^{-1}(f(A)) \supset A$.
Also, $f^{-1}(\cap_j B_j) = \cap_j f^{-1} (B_j)$
$f^{-1}(\cap_j B_j) = \cap_j f^{-1} (B_j)$,
$f^{-1}(B^c) = f^{-1}(B)^c$. However, $f$ as a map on sets does not behave
that well (fortunately!) because 
$f(\cap A_j) \subset \cap_j f(A_j)$ (equality, in general, fails), but
$f(\cup A_j) = \cup_j f(A_j)$; also, $f(A_2-A_1) \subset f(A_2) - f(A_1)$.

\paragraph{\S}
The set of functions from $X$ into $Y$ is denoted by $Y^X$. The notation
is motivated by the fact that the set of functions from $\{1, \ldots, n\}$ into
$\R$ is ``the same'' as $\R^n$.
Consider, for example, the set of functions from a set $A$ into $\{0,1\}$.
This is denoted as $\{0,1\}^A$. Since there is a one-to-one correspondence
between this set of functions and the collection of subsets $2^A$ of
$A$ (as explained
above), the surprise that you may have just experienced with this new notation
should not be as high.

\paragraph{\S}
If $A \subset \Omega$ the function $\1_A: \Omega \to \R$, defined by
$\1_A(\omega)=1$ if $\omega \in A$, and $0$, otherwise, is the indicator\footnote{
Also called characteristic function, but, mostly, in Analysis. 
In Probability, if $\1_A$ is thought of as a random variable,
it is also called  Bernoulli random variable.}
of the set $A$. Note that $\1_A \1_B = \1_{AB}$, $\1_{A^c} = 1-\1_A$.
If $A \subset B$, then $\1_{B-A} = \1_B - \1_A$. If $AB = \varnothing$
then $\1_{A\cup B} = \1_A + \1_B$.
We can check that the `inclusion-exclusion formula'
$\1_{A \cup B} = \1_A + \1_B - \1_{AB}$ holds for arbitrary $A, B$,
by (if we want to be slick) using
$(1-\1_A)(1-\1_B) = 1-\1_A-\1_B+\1_A \1_B$ and using the
fact that $\1_A \1_B = \1_{AB}$  while
$(1-\1_A)(1-\1_B) = \1_{A^c} \1_{B^c} = \1_{A^c B^c}
= \1{(A \cup B)^c} = 1-\1_{A \cup B}$.
The inclusion-exclusion formula for many sets follows
by expanding the product $(1-\1_{A_1}) \cdots (1-\1_{A_n})$.


\paragraph{\S}
Often, sets have elements which are themselves sets. 
(For example, the set of all sets of dishes in a shop.)
When we talk about sets of sets we
refer to them as classes (or collections, or systems, or aggregates)
of sets.\footnote{
For philological, rather than mathematical, reasons
}


\paragraph{\S}
A class of sets $\RR \subset 2^\Omega$ is a $\pi$-system
if it is closed under pairwise intersections ($A, B \in \RR \Rightarrow
AB \in \RR$).
If $\AA \subset 2^\Omega$ then the intersection
of all $\pi$-systems containing $\AA$ is a $\pi$-system
and is denoted by $\pi(\AA)$.


\paragraph{\S}
A class of sets $\DD \subset 2^\Omega$ is a $\lambda$-system
%if it contains $\Omega$ and
if it is closed under increasing differences ($A, B \in \DD ,
A \subset B \Rightarrow AB \in \DD$),  and increasing
limits ($A_n \in \DD, A_n \subset A_{n+1}$, for all $n$, $\Rightarrow \cup_n
\in \DD$).
If $\AA \subset 2^\Omega$ then the intersection
of all $\lambda$-systems containing $\AA$ is a $\lambda$-system
and is denoted by $\lambda(\AA)$.


\paragraph{\S}
A class of sets $\CC \subset 2^\Omega$ is a field (or algebra) 
if it is a $\pi$ system containing $\Omega$ and
such that $A \in \CC \Rightarrow A^c \in \CC$.
(Therefore, a field is closed under unions and any finite number of
operations on its elements.)
If $\AA \subset 2^\Omega$ then the intersection
of all fields containing $\AA$ is a field.


\paragraph{\S}
A class of sets $\FF \subset 2^\Omega$ is a $\sigma$-field 
(or $\sigma$-algebra)\footnote{The letter $\sigma$ is supposed to mean ``sum''
and, in fact, a ``sum'' of countably many objects; in the case at hand
it represents ``countable unions''}
if it is a field and if
$A_1, A_2, \ldots \in \FF \Rightarrow \cap_{j=1}^\infty A_j \in \FF$.
If $\AA \subset 2^\Omega$ then the intersection
of all $\lambda$-systems containing $\AA$ is a $\sigma$-field
and is denoted by $\sigma(\AA)$.




%\paragraph{\S}
%If $A \subset \R$ then $\sup A$ is the least of all 
%$b \in \R \cup \{+\infty\}$ such that $a \le b$ for all $a \in b$.
%We let $\inf A = -\sup(-A)$, where $-A=\{-a: a \in A\}$.
%If $x_n$, $n=1,2, \ldots$ is a countable collection of real numbers (i.e.\
%a sequence) then $\sup x_n$ is written in lieu of $\sup\{x_1, x_2, \ldots\}$.
%Similarly, for $\inf x_n$.
%The upper limit of $x_n$ is defined by $\limsup_{n \to \infty} x_n
%= \inf_{n \ge 1} \sup_{k \ge n} x_k$.
%The lower limit is defined by $\liminf_{n \to \infty} x_n
%= - \limsup_{n \to \infty} (-x_n)$.
%The sequence converges (in an extended sense) if $\limsup x_n
%= \liminf x_n$. This common number is denoted as $\lim_{n \to \infty}
%x_n$ and can be a real number of $\pm \infty$. We say that the sequence
%converges (in a real sense) if $\limsup x_n
%= \liminf x_n$ and this common number is a real number.

\paragraph{\S}
If $\{\FF_j\}$ is a collection of $\sigma$-fields on the same set
then $\cap_j \FF_j$ is a $\sigma$-field too: it is the largest
$\sigma$-field contained in all of them.
(The intersection of $\sigma$-fields is never empty because every
$\sigma$-field contains the empty set.)
However the union of $\sigma$-fields is not a nice object and we
don't consider it. Instead, we define $\vee_j \FF_j$ to
be the smallest $\sigma$-field containing all the $\FF_j$.
\paragraph{\S}
If $A, B$ are sets, then $A \times B$ is the set of all ordered
pairs $(a,b)$ where $a \in A$ and $b \in B$. 
%One may wonder
%what an ordered pair is, but one may define it as $\{a, \{a,b\}\}$.
Similarly, if $\{A_j, j \in \N\}$ is a sequence of sets
then $\bigtimes_{j=1}^\infty A_j$ is the set of all 
sequences $(a_1, a_2, \ldots)$ where $a_j \in A_j$ for 
all $j$.
Finally, if $\{A_t, t \in T\}$ is an arbitrary collection of sets
we may defined $\bigtimes_{t \in T} A_t$ as the collection of
functions $f \in A^T$, where $A=\cup_{t \in T} A_t$ such that
$f(t) \in A_t$ for all $t \in T$.
Notice that this definition does not respect any ``order'' in the index
set $T$ even if this is there; the order imposed in the definition
of the Cartesian product of finitely or countably many sets
is an extra bag that we have been forced to carry (for good reasons).
When $A = \bigtimes_{j \in J} A_j$ is a Cartesian product, we can define,
for each $i\in J$,  the projection function
$\rho_i : A \to A_i$ by $\rho_i: (a_j, j \in J) \mapsto a_i$.


\paragraph{\S}
Let $(\Omega_1, \FF_1)$, $(\Omega_2, \FF_2)$ be measurable spaces.
Then $\FF_1 \otimes \FF_2$ is 
the $\sigma$-field on $\Omega_1 \times \Omega_2$
generated by sets of the form $A_1 \times A_2$, where $A_1 \in \FF_1$,
$A_2 \in \FF_2$.
It also equals $\sigma(\rho_1, \rho_2)$, where $\rho_1, \rho_2$ are
the projection functions.
It also equals the smallest $\sigma$-field containing 
the $\sigma$-field $\{A_1 \times \Omega_2:~ A_1 \in \FF_1\}$
and the $\sigma$-field $\{\Omega_2 \times A_2:~ A_2 \in \FF_2\}$.
The definition is extended for any finite product.

\paragraph{\S}
The Borel $\sigma$-field $\BB$ on $\R$ is the $\sigma$-field
generated by the class of open sets. (A set $O$ is open if for any
any $x \in O$ there is an $\epsilon > 0$ such that $[x-\epsilon, x+\epsilon]
\in O$.)
It is also generated by intervals of the form $(a,b), a, b \in \R$.
It is also generated by intervals of the form $[a,b], a, b \in \R$.
It is also generated by intervals of the form 
$(-\infty, x]$, $x \in \R$.
(This last class of intervals forms a $\pi$-system.) 
The Borel $\sigma$-field $\BB(\R^2)$ on $\R^2 = \R \times \R$
is defined by $\BB(\R^2) = \BB \otimes \BB$.
Similarly, we define $\BB(\R^d)$ for any natural number $d$,
as $\BB(\R^d) = \BB(\R^{d-1}) \otimes \BB$, by induction on $d$.
Notice that $\BB(\R^d)$ is also generated by open sets in $\R^d$. 
(A set $O \subset \R^d$ is open if for any $x=(x_1, \ldots, x_d) \in
\R^d$ there is an $\epsilon > 0$ such that the cube
$[x_1-\epsilon, x_1+\epsilon] \times \cdots \times
[x_d-\epsilon, x_d+\epsilon] \in O$.)

\paragraph{\S}
Let $(S_i, \SS_i)$, $i \in \N$ be measurable spaces,  and let
$S= \bigtimes_i S_i$.
A rectangle is a subset of $S$ of the form
$B_1 \times \cdots \times B_j \times \cdots$ with $B_i \in \SS_i$ for all $i$.
A finite-dimensional rectangle is a rectangle such that
$B_k = S_k$ for all $k$ greater than some index $j$.
A cylinder set is a subset of $S$ of the form
$A \times S_{j+1} \times S_{j+2} \times \cdots$, where
$A \in \SS_1 \otimes \cdots \otimes \SS_j$.
A finite-dimensional rectangle is a rectangle and a cylinder set.
A rectangle is not necessarily a cylinder set.
The collection of rectangles is $\pi$-system (the intersection of two rectangles
is still a rectangle; but the union of two rectangles is not a rectangle;
the complement of a rectangle is not a rectangle).
Ditto for finite-dimensional rectangles.
The collection of cylinder sets is a field (the intersection of
two cylinder sets is a cylinder set and the complement of a cylinder
set is a cylinder set), but not a $\sigma$-field.
On $S$ we can put a natural $\sigma$-field, denoted by $\bigotimes_i \SS_i$:
it is the $\sigma$-field generated by cylinder sets; it is also
generated by rectangles; it is also generated by finite-dimensional rectangles;
it is also the smallest $\sigma$-field such that every projection
$\pi_i : (S, \SS) \to (S_i, \SS_i)$ is a random variable.

%If $A$ is a finite set then $\sharp A$ is the number of its elements (its
%cardinality).

\paragraph{\S}
Let $A_n$ be a sequence of subsets of $\Omega$. We define\footnote{
Notice the complete analogy with numerical sequences: 
$\limsup_{n \to infty} x_n = \inf_n \sup_{k \ge n} x_k$,  
$\liminf_{n \to infty} x_n = \sup_n \inf_{k \ge n} x_k$;
and $x_n \to x$, as $n \to \infty$, if and only if $\limsup x_n
= \liminf x_n =x$; the limit $x$ could be $\pm \infty$.
}
\[
\limsup_{n \to \infty} A_n = \cap_n \cup_{m\ge n} A_m,
\quad
\liminf_{n \to \infty} A_n = \cup_n \cap_{m\ge n} A_m,
\]
and notice that $(\limsup_{n \to \infty} A_n)^c 
=\liminf_{n \to \infty} A_n^c$. 
We say that $\lim_{n \to \infty} A_n = A$ (we also write $A_n \to A$)
if, by definition,
$\limsup_{n \to \infty} A_n =  \liminf_{n \to \infty} A_n=A$,
and write this also as $A_n \to A$.
For example, if $A_n$ is an increasing sequence of sets then (show this!)
$\lim_{n \to \infty} A_n = \cup_n A_n$ and if $A_n$ is decreasing
then $\lim_{n \to \infty} A_n = \cap_n A_n$.
Also notice that $\omega \in \limsup A_n$ if and only if $\omega$ belongs
to $A_n$ for infinitely many indices $n$, while
$\omega \in \liminf A_n$ if and only if $\omega$ belongs to
$A_n$ for all except finitely many $n$. 



\paragraph{\S}
If $\SS$ is a $\lambda$-system and $A \subset \Omega$ then
\[
\SS_A := \{B \in 2^\Omega:~ BA \in \SS\}
\]
is also a $\lambda$-system.
Indeed, if $B_1 \subset B_2$ both belong to $\SS_A$ then
$B_1A, B_2A$ belong to $\SS$ and $(B_2-B_1)A =B_2A - B_1A \in \SS$,
because $\SS$ is closed under proper differences; 
so $B_2-B_1 \in \SS_A$.
Also, if $B_n \in \SS_A$, $B_n \subset B_{n+1}$ for all $n$, 
then $B_nA \in \SS$ for all $n$, and so 
$A\cup_n B_n = \cup_n AB_n \in \SS$ because $\SS$ 
is closed under increasing limits; so $\sup_n B_n \in \SS_A$.

\paragraph{\S}
$\pi$ \& $\lambda$ \& $\Omega \equiv \sigma$. In other words,
if $\SS$ is both $\pi$ and $\lambda$ and contains $\Omega$
then it is a $\sigma$-field.
Indeed, if $A \in \SS$ then $A^c = \Omega-A \in \SS$ because $\SS$ is
$\lambda$. So $\SS$ is closed under complementations, intersections
and limits. So it is a $\sigma$-field.


\paragraph{\S [Sierpi\'nski-Dynkin Lemma]}
Let $\SS$ be a $\pi$-system containing $\Omega$.
Then $\lambda(\SS) = \sigma(\SS)$.

\no\proof
Since $\lambda(\SS)$ is the smallest $\lambda$-system containing $\SS$
and since $\sigma(\SS)$ is a $\lambda$-system, we have $\lambda(\SS)
\subset \sigma(\SS)$.
We need to show that $\sigma(\SS) \subset \lambda(\SS)$. If we show
that $\lambda(\SS)$ is also a $\pi$-system then it will be
a $\sigma$-field and we'll be done.
We know that
\begin{equation}
\label{nada}
A \in \SS,~ B \in \SS \Rightarrow AB \in \SS \subset \lambda(\SS).
\end{equation}
Hence
\[
\forall A \in \SS \quad \SS \subset \{B \in 2^\Omega: AB \in \lambda(\SS)\}
=: \lambda(\SS)_A.
\]
But $ \lambda(\SS)_A$ is $\lambda$ and so
\[
\forall A \in \SS \quad  \lambda(\SS)  \subset  \lambda(\SS)_A.
\]
Let's read this again:
\begin{equation}
\label{nada2}
 A \in \SS, ~ B \in  \lambda(\SS) \Rightarrow AB \in \lambda(\SS).
\end{equation}
Wonder of wonders: \eqref{nada} implied the seemingly stronger \eqref{nada2}.
Let's rewrite the \eqref{nada2} as:
\[
\forall B \in \lambda(\SS) \quad \SS \subset
\{A \in 2^\Omega:~ AB \in \lambda(\SS)\}=: \lambda(\SS)_B.
\]
But $ \lambda(\SS)_B$ is $\lambda$ and so
\[
\forall B \in \lambda(\SS) \quad \lambda(\SS)  \subset  \lambda(\SS)_B.
\]
Let's read this again:
\begin{equation}
\label{nada3}
B \in \lambda(\SS), ~ A \in \lambda(\SS) \Rightarrow AB \in \lambda(\SS).
\end{equation}
Wonder of wonders of wonders: \eqref{nada2} implied the seemingly stronger
\eqref{nada3} which is what we need.
\qed






\section{APPENDIX B: Sets and numbers}

In some sense, probability is all about assigning numbers to sets.

\paragraph{\S}
Let $\Omega$ be a set and $\CC$ a field of subsets of it.
The function $\Pr_0: \CC \to [0,1]$ is additive if
$\Pr_0(A \cup B) = \Pr_0(A)+\Pr_0(B)$ whenever $AB = \varnothing$.
It is countably additive if for any $A \in \CC$ for which
there exist mutually disjoint $A_n \in \CC$ with $A = \cup_n A_n$
we have $\Pr_0(A) = \sum_n \Pr_0(A_n)$.
We will throughout assume that $\Pr_0(\Omega)=1$. 
(If, in addition to the above, we have that $\CC$ is a $\sigma$-field,
then $\Pr_0$ is a probability.)



\paragraph{\S}
If $\Pr$ is a probability on $(\Omega, \FF)$, then $(\Omega, \FF, \Pr)$
is called probability space.
If $A_n$ is a sequence of sets in $\FF$ then $\Pr(\cup_n A_n)
\le \sum_n \Pr(A_n)$ [Boole's inequality].
If $A_n \to A$ as $n \to \infty$
then $\Pr(A_n) \to \Pr(A)$ as $n \to \infty$ [continuity].
If $\sum_n \Pr(A_n) < \infty$ then $\Pr(\limsup A_n) =0$.
[Borel-Cantelli lemma]. (Proof: $\cup_{k \ge m} A_k \to \limsup A_n$,
as $m \to \infty$; So $\Pr(\limsup_n A_n) = \lim_{k \ge m}
\Pr(\cup_{k \ge m} A_k)$. But the latter is $\le \sum_{k \ge m} \Pr(A_k)$
which tends to $0$, as $m \to \infty$, by the assumption.)


\paragraph{Lemma \small [CA]}
The following are equivalent:
\\
(i)
$\Pr_0$ is countably additive on the field $\CC$.
\\
(ii)
$\Pr_0(A_n) \to 0$ for all decreasing sequences $A_n \in \CC$ with
$\cap_n A_n=\varnothing$.
\\
(iii)
$\Pr_0(A_n) \to 0$ for all sequences $A_n \in \CC$ with
$A_n \to \varnothing$.

\noindent\proof
Suppose (i) holds. Let $A_n$ decrease to $\varnothing$. We have
\begin{align*}
\Pr_0(A_1) &= \sum_{k=1}^\infty \Pr_0(A_k - A_{k+1})\\
&= \lim_{n \to \infty} \sum_{k=1}^{n-1} [\Pr_0(A_k)-\Pr_0(A_{k+1})]
\\
&= \lim_{n \to \infty} [\Pr_0(A_1)-\Pr_0(A_n)],
\end{align*}
i.e.\ $\Pr_0(A_n) \to 0$. We proved (i) $\Rightarrow$ (ii).
Next, suppose (ii) holds. Let $A_n$ be mutually disjoint elements
of $\CC$ with $\cup_n A_n \in \CC$. By finite additivity,
\[
\Pr_0(\cup_k A_k) = \sum_{k=1}^n\Pr_0(A_k) + \Pr_0(\cup_{k>n} A_k).
\]
Since $\cup_{k>n} A_k$ decreases to $\varnothing$ we have
$\Pr_0(\cup_{k>n} A_k) \to 0$, and so we obtain countable additivity.
We proved (ii) $\Rightarrow$ (i).
Suppose (ii) holds. Let $A_n \in \CC$, $A_n \to \varnothing$.
We want to show that $\Pr_0(A_n) \to 0$. The problem is that $A_n$ is not
decreasing so we need, somehow, to construct auxiliary decreasing
sequence of sets. What does $A_n \to \varnothing$ mean? It means that
\[
G_n := \cup_{k \ge n} A_k \downarrow \varnothing.
\]
If we knew that $G_n \in \CC$ we would immediately get the result.
The problem is we don't know that, so we can't use $G_n$ as an argument
of the function $\Pr_0$. We need to work harder. We only know that finite
unions belong to $\CC$. So let us approximate $G_n$. We have
\[
G_{n,r} := \cup_{k=n}^r A_k \uparrow G_n, \quad
\text{ as } r \to \infty.
\]
We also know that $G_{n,r} \in \CC$ for all $n, r$. So we can talk
about $\Pr_0(G_{n,r})$, a numerical sequence which increases with $r$
(and bounded below 1), having a limit, say
\[
\gamma_n = \lim_{r \to \infty} \Pr_0(G_{n,r}).
\]
This means that, FOR EACH $n$,
$\Pr_0(G_{n,r})$ differs from $\gamma_n$ by anything
we like, when $r$ is large. 
Let $\epsilon_n$ be this ``anything we like'' thing.
We just said that 
\[
\text{ FOR ALL } n, \quad \gamma_n - \Pr_0(G_{n,r}) \le \epsilon_n,
\quad \text{ for all $r$ larger than or equal to some $r(n)$}.
\]
In particular,
\[
\text{ FOR ALL } n, \quad \gamma_n - \Pr_0(G_{n,r(n)}) \le \epsilon_n.
\]
And if we let
\[
R(n) := \max(r(1), r(2), \ldots, r(n),n),
\]
we have
\[
\text{ FOR ALL } n, \quad \gamma_n - \Pr_0(G_{n,R(n)}) \le \epsilon_n.
\]
%because $r(n) \le R(n)$ and so $\Pr_0(G_{n,R(n)}) \le \Pr_0(G_{n,r(n)})$.
Moreover, the sequence $R(n)$ is increasing.
We have  
\[
A_n \subset G_{n,R(n)} \subset G_n \downarrow \varnothing,
\]
so, while we have created a sequence $G_{n,R(n)}$ of sets in $\CC$ which
is above $A_n$, and does converge to $\varnothing$, we do not know
that $G_{n,R(n)}$ decreases, so we cannot apply our assumption (ii).
Therefore we need to work harder. We take
\[
H_n = \cap_{k=1}^n G_{k,R(k)}.
\]
Clearly, $H_n \in \CC$, and $H_n$ decreases, and $H_n \downarrow 
\varnothing$, therefore, by (ii),
\[
\Pr_0(H_n) \to 0.
\]
But how does $H_n$ compare to $A_n$? We lost track of it, so let's see:
\begin{align*}
\Pr_0(A_n \setminus H_n) 
&= \Pr_0\left(\cup_{k=1}^n \big(A_n \setminus G_{k,R(k)}\big) \right)
\\
&\le \sum_{k=1}^n 
\Pr_0\left(A_n \setminus G_{k,R(k)}\right)
\\
&\le \sum_{k=1}^n  
\Pr_0\left(G_{n,R(n)} - G_{k,R(k)} \right)
\\
&\le \sum_{k=1}^n  
\big( \Pr_0(G_{k,R(n)}) - \Pr_0(G_{k,R(k)}) \big)
\\
&\le \sum_{k=1}^n
\big( \epsilon_k - \Pr_0(G_{k,R(k)}) \big)
\le \sum_{k=1}^n \epsilon_k,
\end{align*}
where, recall, $\epsilon_k$ is ANYTHING WE PLEASE. We would be pleased to
show that $\Pr_0(A_n \setminus H_n) \to 0$, for this would imply
$\Pr_0(A_n) \to 0$. Let us then CHOOSE 
\[
\epsilon_k = \eta 2^{-k},
\]
where $\eta >0$ is arbitrary.
Hence $\sum_{k=1}^n \epsilon_k \le \eta$. Hence $\Pr_0(A_n \setminus H_n)
\le \eta$, and so we can conclude. We proved that (ii) $\Rightarrow$ (iii).
Since, obviously, (iii) $\Rightarrow$ (ii), the lemma has been proved.
\qed


\paragraph{Lemma \small [COMMON LIMITS]}
Suppose that $\Pr_0$ is countably additive on the field $\CC$.
\\
(i)
If $A_n$ is a sequence in $\CC$ that has a limit (but which is not
necessarily in $\CC$, then $\Pr_0(A_n)$ has a limit.
\\
(ii)
If $A_n$, $B_n$ are sequences in $\CC$ with the same limit (not
necessarily in $\CC$) then $\Pr_0(A_n)$, $\Pr_0(B_n)$
have the same limit.

\no\proof
Recall that a sequence $x_n$ of real numbers converges if and only
if, given $\epsilon > 0$, there is an integer $N$ such that
$\sup_{m > n}|x_n-x_m| \le \epsilon$ if $n > N$.
The negation of the latter statement implies the existence of
$\epsilon > 0$ such that, for all $N$ there is $n > N$ and $m > N$
with $|x_n -x_m| > \epsilon$; or, if we let $m=I(n)$, we have
that $|x_n-x_{I(n)}| \not \to 0$, as $n \to \infty$.
Therefore, if we can prove that for \underline{all} strictly increasing
sequence of integers $I(n)$ we have
\[
x_n - x_{I(n)} \to 0, \quad \text{ as } n \to \infty,
\]
we can deduce that $x_n$ has a limit.
Let $I(n)$ be such a sequence. Then
\[
|\Pr_0(A_n) - \Pr_0(A_{I(n)}| \le |\Pr_0(A_n \xor A_{I(n)}| .
\]
But $A_n$ has a limit. Therefore $A_n \xor A_{I(n)} \to \varnothing$.
By the Lemma above, $\Pr_0(A_{I(n)} \to 0$, and so (i) Is proved.
To prove (ii), we use the same reasoning but with $B_{I(n)}$ instead
of $A_{I(n)}$.
\qed


\paragraph{Lemma \small [FIRST EXTENSION]}
Suppose that $\Pr_0$ is countably additive on the field $\CC$.
Let $D(\CC)$ be the class of subsets of $\Omega$
that are limits of sets in $\CC$.
Define $\Pr_1$ on $D(\CC)$ by
\[
\Pr_1(\lim_n A_n) = \lim_n \Pr_0(A_n), \quad A_n \in \CC.
\]
Then
\\
(i)
$D(\CC)$ is a field.
\\
(ii)
The definition $\Pr_1$ is valid.
\\
(iii)
$\Pr_1$ is countably additive on $D(\CC)$.

\no\proof
(i) Easy.
\\
(ii) Follows from {Lemma \small [COMMON LIMITS]}. 
\\
(iii)
From Lemma [CA], it suffices to show that if $A_n$ is a sequence of
elements of $D(\CC)$ such that $A_n \downarrow \varnothing$
then $\Pr_1(A_n) \to 0$.
Since $A_m \in D(\CC)$ we can write
\[
A_m = \lim_n B_{m,n}.
\]
Then we also have
\[
A_m = \lim_n (B_{1,n} \cap \cdots \cap B_{m,n}).
\]
Choose a sequence of integers $n_m$ increasing
to $\infty$ such that
\[
\lim_m [\Pr_1(A_m) - \Pr_0(B_{1,n_m} \cap \cdots \cap B_{m,n_m})]=0.
\]
Since
\[
\lim_m (B_{1,n_m} \cap \cdots \cap B_{m,n_m}) = \varnothing,
\]
we have
\[
\lim_m \Pr_0(B_{1,n_m} \cap \cdots \cap B_{m,n_m})=0,
\]
and so 
\[
\lim_m \Pr_1(A_m) =0.
\]
\qed




\paragraph{Lemma \small [SECOND EXTENSION]}
Suppose that $\Pr_0$ is countably additive on the field $\CC$.
Let $D(\CC)$ be the class of subsets of $\Omega$
that are limits of sets in $\CC$.
Let $D^2(\CC)$ be the class of subsets of $\Omega$
that are limits of sets in $D(\CC)$.
Define $\Pr_2$ on $D^2(\CC)$ by
\[
\Pr_2(\lim_n A_n) = \lim_n \Pr_1(A_n), \quad A_n \in D(\CC).
\]
Then
(i)
$D^2(\CC)$ is a field.
\\
(ii)
The definition $\Pr_2$ is valid.
\\
(iii)
$\Pr_2$ is countably additive on $D^2(\CC)$.

\no\proof
Repetition of the proof of {Lemma \small [FIRST EXTENSION]}.
\qed





\paragraph{Proposition \small [SANDWICH]}
\label{PB5}
Let $\FF$ be the $\sigma$-field generated by $\CC$. Then, for any $B \in \FF$,
there are $A, C \in D^2(\CC)$ such that $\Pr_2(A) = \Pr_2(C)$ and $A \subset B
\subset C$.

\no\proof
Let $D^\downarrow(\CC)$ (respectively, $D^\uparrow(\CC)$)
be the class of sets which are limits
of decreasing (respectively, increasing) sequences of sets of $\CC$.
Define the class $\DD$ of subsets of $\Omega$ for which,
given $\epsilon > 0$,
there is $G \in D^\downarrow(\CC)$ and
$H \in D^\uparrow(\CC)$
such that
\[
G \subset A \subset H, \quad
\Pr_1(H)-\Pr_1(G) < \epsilon.
\]
We have $\CC \subset \DD$. Also, $\Omega \in \DD$.
So if we show that $\DD$ is both $\pi$ and $\lambda$, then
it is $\sigma$ and so $\sigma(\CC) \subset \DD$ and we are done.
That it is closed under intersections and proper differences
is easy. That it is closed under increasing limits is left as an exercise.
\qed

}
%%%% END APPENDIX %%%%








\end{unit}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{4}{Joint distributions and independence}
% SYLLABUS:
%4.  Joint distributions and independence.                               TK
%      Joint distributions, 	DONE
% marginal 	DONE
% and conditional  distributions.	DONE
% Independence: DONE
% factorisation of joint distribution and moment generating function, DONE
% moment properties. [What does this mean???]
%      Covariance, correlation, DONE [L2 approach]
% multivariate normal distribution.	DONE

\section{Introduction}
Most of this chapter is concerned with a random variable $(X,Y)$
with values in $\R^2$, but the concepts/results
are easily generalisable to random variables with values in $\R^d$.

We first explain why the joint distribution function defines the law
of $(X,Y)$. We talk about independence and carefully explain
why independence between classes of sets closed under intersection
implies independence between their $\sigma$-fields.

To define conditional density we define projection and prove everything,
except the existence of a regular conditional distribution.

Finally, we talk about a Gaussian variable in $\R^d$.

\section{Joint distributions}
Consider a random variable $(X, Y): (\Omega, \FF) \to (\R^2, \BB(\R^2))$.
This random variable is called TWO RANDOM VARIABLES. 
\begin{quote}
If
$\Pr$ is a probability of $(\Omega, \FF)$, the joint distribution of 
$(X,Y)$ is another name for the law $\Pr_{X,Y}$ of the
random variable $(X,Y)$. 
\end{quote}
The joint distribution function of $(X,Y)$
is the function
\begin{equation}
\label{jdf}
F_{X,Y}(x,y) := \Pr(X \le x, Y \le y) = \Pr_{X,Y}
((-\infty, x] \times (-\infty, y]), \quad (x,y) \in \R^2.
\end{equation}
The law $\Pr_X$ of $X$ is referred  to as the first marginal
of the law $\Pr_{X,Y}$.
The distribution function $F_X$ of $X$ is referred to as the
first marginal distribution function of the joint 
distribution function $F_{X,Y}$ and, of course,
\[
F_X(x) = \lim_{y \to \infty} F_{X,Y}(x,y).
\]
Note that we chose ti use $\le$ instead of $<$ in \eqref{jdf} for
no good reason other than a mere arbitrary convention.


\subsection{Knowledge of $F_{X,Y}$ implies knowledge of $\Pr_{X,Y}$}
We would like to explain why, knowledge of the function $F_{X,Y}$
implies knowledge of $\Pr_{X,Y}(B)$ for all $B \in \BB(\R^2)$.
Consider a rectangle (with sides parallel to the axes--please think
geometrically)
\begin{equation}
\label{rrr}
(a_1, b_1] \times (a_2, b_2] :=
\{(x,y) \in \R^2:~ a_1 < x \le b_1, ~ a_2 < y \le b_2\}.
\end{equation}
We allow $a_1$, $a_2$ to take any value, including $-\infty$.
Since $(-\infty, b_1] \times (-\infty, b_2]$ is the
disjoint union of four rectangles, using additivity, we obtain
\[
\Pr_{X,Y}((a_1, b_1] \times (a_2, b_2])
= F_{X,Y}(b_1, b_2) 
- F_{X,Y}(b_1, a_2)
- F_{X,Y}(a_1, b_2)
+ F_{X,Y}(b_1, b_2).
\]
Rectangles of the form \eqref{rrr} have the following nice properties:
First, intersection of two of them is a rectangle
of the same form. Thus, if $\RR$ denotes the collection
of these rectangles we have that $\RR$ is closed under finite intersection,
i.e.\ it is a $\pi$-system. Second, the complement of
a rectangle from $\RR$ is a finite union of disjoint rectangles from $\RR$.
\begin{exe}
Write, explicitly, the complement of $(a_1, b_1] \times (a_2, b_2]$
as the disjoint union of elements of $\RR$.
Notice we can do that in at least two different ways.
Do so.
\end{exe}
Now consider the class
\[
\CC := \{\text{finite disjoint unions of elements of $\RR$} \}.
\]
It is easy to visualise, geometrically, what kind of elements
$\CC$ contains.
Then
\begin{exe}
Show that $\CC$ is a field, i.e.\ if $A \in \CC$ then $A^c \in \CC$ and
if $A, B \in \CC$ then $A \cup B \in \CC$.
\end{exe}
Note that the notation used here mimics that of Section \ref{toss}.
Indeed, the classes $\RR, \CC$ here behave in the same way as
the classes with the same names there.

Hence, if $A \in \CC$, we can write $A = \cup_{i=1}^m B_i$, where
$B_i$ are disjoint rectangles from $\RR$, and, since for
each such rectangle $B_i$ we can use $F_{X,Y}$ to compute 
$\Pr_{X,Y}(B)$, we have that
\[
\Pr_{X,Y}(A) = \sum_{i=1}^m \Pr_{X,Y}(B), \quad A \in \CC,
\]
can be computed by using $F_{X,Y}$ only.

But there are many sets in $\BB(\R^2)$ that do not belong to $\CC$,
so we wish to continue our endeavour. 
If it were true that every set in $\BB(\R^2)$ was a limit of
sets of $\CC$ then we would be finished, by the continuity
property of a probability. However, there are many elements in
$\BB(\R^2)$ that are not limits of sets in $\CC$.
\begin{example}
The set of all points $(x,y)$ where $x, y$ are rationals cannot be obtained
as a limit of elements of $\CC^2$. To illuminate this point,
consider ``straightforward'' procedure that places a little rectangle
around each such point and then let the little rectangle
shrink. Specifically, let $\Q=\{q_1,q_2, \ldots\}$ be an enumeration
of the rationals. To each $(q_m, q_n)$ associate the rectangle
\[
I_{m,n}(\epsilon) := (q_m - \epsilon 2^{-m}, ~q_m + \epsilon 2^{-m}]
\times
(q_n - \epsilon 2^{-n}, ~q_n + \epsilon 2^{-n}],
\]
and let $I(\epsilon) := \cup_{m,n} I_{m,n}(\epsilon)$.
Show that $\cap_{\epsilon > 0, \epsilon \in \Q} I(\epsilon)$
is not equal to $\Q\times \Q$.\\
{\em Hint: The set $I(\epsilon)$ is uncountable.}
\end{example}

We will denote by $\Pr_0$ the function $\Pr_{X,Y}$ restricted
to $\CC$.
Clearly, $\Pr_0$ is uniquely specified by $F_{X,Y}$.
If we show that $\Pr_0$ can be uniquely extended to
a probability on $(\RR^2, \BB(\R^2))$ then our claim that $F_{X,Y}$
completely specifies $\Pr_{X,Y}$ will be proved. 
The steps in showing this are precisely the same as those of
Section \ref{toss}.\\
1. We first show that $\Pr_0$ is countably additive on $\CC$.
\\
2. We then extend $\Pr_0$ to $\Pr_1$ on $D(\CC)$.
\\
3. We then extend $\Pr_1$ to $\Pr_2$ on $D^2(\CC)$.
\\
4. Finally, we show, precisely as before, that,
%Let $D(\CC)$ be those sets that are limits of elements of $\CC$.
%Clearly, for every $A \in D(\CC)$ we can compute $\Pr_{X,Y}(A)$
%based on knoledge of $F_{X,Y}$ alone.
%Let $D^2(\CC)$ be those sets that are limits of elements of $D(\CC)$.
%Again, for every $A \in D(\CC)$ we can compute $\Pr_{X,Y}(A)$
%based on knoledge of $F_{X,Y}$ alone.
%\begin{exe}
%Show that  closed rectangle is in $D(\CC)$.
%\end{exe}
%As sketched in Appendix B of the previous chapter,
%$D(\CC)$ is a field.  
%
%One might suspect that, by induction, i.e.\
%by considering $D^k(\CC)$, for $k=1,2,\ldots$
%we will exhaust all elements of
%$\BB(\R^2)$. Unfortunately, this is not the case. Fortunately,
%however, we do have the following (see \cite{fg}):
%\begin{lemma}
for every $B \in \BB(\RR^2)$ there are sets $A, C \in D^2(\CC)$ such
that $A \subset B \subset C$ and $\Pr_2(A) = \Pr_2 (C)$.
%Clearly then, $\Pr_{X,Y}(B) = \Pr_{X,Y}(A)$ and, since the
%latter can be computed via $F_{X,Y}$ alone, so can the former.

\section{Independence}
Recall (see \fbox{2.2}) that $X, Y$ are independent random variables
on $(\Omega, \FF \Pr)$ if $\sigma(X)$, $\sigma(Y)$ are independent 
$\sigma$-fields.
We wish to show that
\begin{proposition}
\label{prodf}
$X, Y$ are independent on $(\Omega, \FF, \Pr)$ if and only if
$F_{X,Y}(x,y) := \Pr(X \le x, Y \le Y)$,
$F_X(x) := \Pr(X \le x)$, 
$F_Y(y) := \Pr(Y \le y)$ are related by
\[
F_{X,Y}(x,y) = F_X(x) F_Y(y).
\]
\end{proposition}
This is a consequence of the following:
\begin{lemma}
\label{indpi}
Let $(\Omega, \FF, \Pr)$ be a probability space.
Let $\RR_1, \RR_2$ be two $\pi$-systems.
Then $\sigma(\RR_1), \sigma(\RR_2)$ are independent if and only if
\[
\Pr(B_1 B_2) = \Pr(B_1) \Pr(B_2),
\quad
B_1 \in \RR_1, ~ B_2 \in \RR_2.
\]
\end{lemma}
\begin{proof}
The proof mimics the uniqueness part of the proof of Theorem \ref{ouf}.
Fix $B_1 \in \RR_1$ and consider two probabilities on $\sigma(\RR_2)$:
\[
\Pr(B_1 A_2), \quad \Pr(B_1) \Pr(A_2), \quad A_2 \in \sigma(\RR_2).
\]
Our assumption says that these two probabilities agree on $\RR_2$.
Since $\RR_2$ is a $\pi$-system, the two probabilities agree
on $\sigma(\RR_2)$: For each $B_1 \in \RR_1$,
\begin{equation}
\label{zaq}
\Pr(B_1 A_2) = \Pr(B_1) \Pr(A_2), \quad A_2 \in \sigma(\RR_2).
\end{equation}
Now, for fixed $A_2 \in \sigma(\RR_2)$ consider two
probabilities on $\sigma(\RR_1)$:
\[
\Pr(A_1 A_2), \quad \Pr(A_1) \Pr(A_2), \quad A_1 \in \sigma(\RR_1).
\]
\eqref{zaq} says that these two probabilities agree on $\RR_1$.
Since $\RR_1$ is a $\pi$-system, the two probabilities agree
on $\sigma(\RR_1)$:
For each $A_2 \in \sigma(\RR_2)$,
\[
\Pr(A_1 A_2) = \Pr(A_1) \Pr(A_2), \quad A_1 \in \sigma(\RR_1),
\]
which is what we need.
\end{proof}

\no{\bf Proof of Proposition \ref{prodf}:}
Let $\RR_1 = \{X^{-1}(a,b]:~a < b\}$, $\RR_2 = \{Y^{-1}(a,b]:~a < b\}$.
These are both $\pi$-systems.
It is easy to see that the assumption $F_{X,Y}(x,y) = F_X(x) F_Y(y)$
implies that $\Pr(B_1 B_2) = \Pr(B_1) \Pr(B_2)$, $B_1 \in \RR_1$,
$B_2 \in \RR_2$. Hence $\Pr(A_1 A_2) = \Pr(A_1) \Pr(A_2)$, $A_1 \in 
\sigma(\RR_1)= \sigma(X)$, $A_2 \in \sigma(\RR_2)=\sigma(Y)$.
\qed

\section{Joint density}
Consider the coin flip space $(\Omega=\{0,1\}^\N, \FF, \Pr)$.
Define the random variables
\[
U_1 := \sum_{n=1}^\infty \frac{\omega_{2n}}{2^n},
\quad
U_2 := \sum_{n=1}^\infty \frac{\omega_{2n-1}}{2^n}.
\]
By applying Lemma \ref{indpi} we can see that $U_1, U_2$ are
independent.

Let $h: (\R^2, \BB(\R^2)) \to (\R, \BB)$ be measurable and 
suppose $h \ge 0$. Define the Lebesgue integral
\[
\int_{\R^2} h(x,y) dxdy := \sum_{n_1,n_2 \in \Z} \E h(U_1+n_1, U_2+n_2),
\]
and, more generally, for any $B \in \BB(\R^2)$,
\[
\int_{B} h(x,y) dxdy := 
\int_{\R^2} h(x,y) \1_B(x,y) dxdy.
\]
If $h$ has no restriction on sign, define 
$\int_{B} h(x,y) dxdy  := \int_{B} h^+(x,y) dxdy - \int_{B} h^-(x,y) dxdy$,
provided not both terms are infinite.
The following theorem connects what one learns in basic Calculus
of Many Variables with what we just defined.

\begin{theorem}
(i) If $h$ is Riemann integrable on a rectangle $R=[a,b] \times [c, d]$ then
its Lebesgue integral on $R$ coincides with its Riemann integral on $R$.\\
(ii) If $h$ is bounded and measurable then it is Riemann integrable on $R$
of the set of discontinuities $D$ of $h$ satisfies $\Pr((U_1, U_2) \in D) =0$.
\end{theorem}

More generally, given two distribution functions $F_1, F_2$ on $\R$,
we can define the product measure $F_1 \times F_2$ on $(\R^2, \BB(\R^2))$
by defining it first on rectangles,
\[
(F_1\times F_2)(B_1 \times B_2) := \Pr(F_1^{-1}(U_1) \in B_1, ~
 F_2^{-1}(U_2) \in B_2),
\]
and then extending it to $\BB(\R^2)$ using the procedure explained earlier.
We can also define the Lebesgue-Stieltjes integral
\[
\int_{\R^2} h~ d(F_1 \times F_2) := \E h(F_1^{-1}(U_1), F_2^{-1}(U_2)).
\]


\begin{theorem}[Fubini]
If $h \ge 0$ or if $\int_{\R^2} |h|~ d(F_1 \times F_2) < \infty$, then
\[
\int_{\R^2} h~ d(F_1 \times F_2)
= \int_{\R} \left( \int_\R h(x,y) F_2(dy) \right) F_1(dx)
= \int_{\R} \left( \int_\R h(x,y) F_1(dx) \right) F_2(dy).
\]
\end{theorem}
\no{\bf Proof [sketch]:}
The statement is obvious when $h(x,y) = \1_{B_1}(x) \1_{B_2}(y)$.
Hence it is obvious for linear combinations of such functions.
The general statement follows from an approximation procedure
relying on an argument based on the Sierpi\'nski-Dynkin lemma.
\qed



Occasionally, it so happens that there exists a function
$f$ such that $F_{X,Y}$ can be written as a Lebesgue integral:
\[
F_{X,Y}(x,y) = \int_{(-\infty, x]\times (-\infty, y]} f(s,t) ds dt.
\]
In such a case, we say that $(X,Y)$ is absolutely continuous (jointly
absolutely continuous, I suppose, if you want to be pedantic)
and that $f_{X,Y}$ is a density.
Using Fubini's theorem, we see that
\[
f_X(x) = \int_{(-\infty, x]} f(s) ds
\]
is a density for $X$
(i.e.\ $X$ is absolutely continuous, and so is $Y$).

Another consequence of Fubini's theorem is:
\begin{lemma}
If $X, Y$ are independent then
\[
\E(XY) = (\E X )(\E Y),
\]
whenever the expectations are defined.
\end{lemma}

And another, useful consequence of Fubini's theorem is:
\begin{lemma}
If $X$ is a positive random variable then
\[
\E X = \int_0^\infty \Pr(X > x) ~ dx.
\]
\end{lemma}

A standard criterion for independence between $X, Y$, for 
absolutely continuous $(X, Y)$, is: 
\begin{lemma}
Suppose that $(X,Y)$ is absolutely continuous. Let $f_{X,Y}$
be a density of $(X,Y)$. Let $f_X, f_Y$ be densities of
$X, Y$, respectively. Then $X, Y$ are independent if and only if
\[
f(x,y) = f_X(x) f_Y(y),
\]
for all $(x,y)$ except, possibly, on a set of measure zero.
\end{lemma}

\section{Joint moment generating function}
When $(X,Y)$ is a random variable in $\R^2$ we can define its
moment generating function by
\[
M_{X,Y}(\eta, \theta) := \E e^{\eta X + \theta Y}, \quad
\eta, \theta \in \R.
\]
whenever it exists.
Let also $M_X, M_Y$ be the moment generating functions of $X, Y$.
One can prove that:
\begin{lemma}
Suppose that $M_{X,Y}$ exists in a (one sided) neighbourhood of zero.
If $M_{X,Y}(\eta, \theta) = M_X(\eta) M_Y(\theta)$ then
$X, Y$ are independent.
\end{lemma}


\section{Correlations}
We now consider random variables $X$ on some probability space
$(\Omega, \FF, \Pr)$ with  $\E X^2 < \infty$. The aggregate of all 
these random variables will be denoted by 
\[
L^2(\Omega, \FF, \Pr).
\]
If $\E X^2 < \infty$, $\E Y^2 < \infty$, then $\E(X+Y)^2 < \infty$
(indeed, $(x+y)^2 \le 2x^2+2y^2$).
This means that if $X, Y \in L^2(\Omega, \FF, \Pr)$ then, for any 
$a, b \in \R$, $aX + bY \in L^2(\Omega, \FF, \Pr)$. Hence 
$ L^2(\Omega, \FF, \Pr)$ is a linear space (a linear subspace of
$\R^\Omega$).
Recall that the covariance between $X$ and $Y$ is defined by
\[
\cov(X,Y) = \E(X-\E X)(Y - \E Y).
\]
Since, for $X_1, X_2, Y \in L^2(\Omega, \FF, \Pr)$, $a_1, a_2 \in \R$,
\[
\cov(a_1 X_1 + a_2 X_2, Y) = a_1 \cov(X_1, Y) + a_2 \cov(X_2, Y),
\]
the covariance is linear in each of its arguments when the other is
kept fixed and it can thus be used to define an inner product:
\[
\langle X, Y \rangle := \cov (X,Y).
\]
We also define the semi-norm
\[
|| X || := \sqrt{\cov(X, X)} = \sqrt{\var(X, X)},
\]
where the word `semi-norm' means that it has the following properties:
\begin{itemize}
\item[1. ]
$|| X || \ge 0$
\item[2. ]
$|| a_1 X_1 + a_2 X_2 || = |a_1|~ ||X_1|| + |a_2|~ ||X_2||$.
\item[3. ]
$||X+Y|| \le ||X|| + ||Y||$.
\end{itemize}
Another name for $||X||$ is `standard deviation'.
We also note that
\begin{itemize}
\item[]
If $||X||=0$ then $\Pr(X=0)=1$.
\end{itemize}
We \underline{cannot} deduce, from $||X||=0$ alone that
$X(\omega) =0$ for all $\omega \in \Omega$, but only
that $X(\omega)=0$ for all $\omega$ except those in a set
of probability zero. If we could deduce that $X(\omega)=0$ for all
$\omega \in \Omega$, we would say that $||\cdot||$ is a norm.
To get around this problem, we merely identify all random variables
in $L^2(\Omega, \FF, \Pr)$ which differ on a set of measure zero:
That is, we let $[X]$ be the set of all $Y$ such that $\Pr(X \not = Y)=0$,
and redefine $L^2(\Omega, \FF, \Pr)$ to be the collection of
all such $[X]$. It is not hard to see that this is still a linear 
space and if we let $||[X]|| := ||X||$ (which is well defined),
then this is a norm.

Being a normed space with an inner product, $L^2(\Omega, \FF, \Pr)$
has a structure much like the geometric structure of the usual
Euclidean space, for instance, Pythagoras' theorem holds:
\[
||X + Y||^2 = ||X||^2 + ||Y||^2
\quad \text{ if } \langle X, Y \rangle =0.
\]
The notion of convergence in $L^2(\Omega, \FF, \Pr)$ is as follows:
We say that $X_n \to X$ if $||X_n-X|| \to 0$, as $n \to \infty$.
With respect to this notion of convergence, the space $L^2(\Omega, \FF, \Pr)$
is complete:
\begin{lemma}
If $X_n$ is a sequence in $L^2(\Omega, \FF, \Pr)$ such that
\[
\sup_{m,n \ge N} ||X_n - X_m|| \to 0 \text{ as } N \to \infty,
\]
then there is $X \in L^2(\Omega, \FF, \Pr)$
such that
\[
||X_m - X|| \to 0 \text{ as } m \to \infty.
\]
\end{lemma}
\begin{proof}
The assumption means that, given any $\epsilon > 0$, we can find 
and index $N(\epsilon)$ such that $||X_n-X_m|| \le \epsilon$ for
all $n, m \ge N(\epsilon)$.
Since we can do this for any $\epsilon$, we can do it for $\epsilon=2^{-1},
2^{-2}, 2^{-3}, \ldots$. Thus, if $\epsilon = 2^{-\ell}$, there
is an index $N_\ell$ such that 
\begin{equation}
\label{kosher}
\text{$||X_n-X_m|| \le 2^{-\ell}$ for all $n, m \ge N_\ell$.}
\end{equation}
Define $M_\ell=\max(N_1, N_2, \ldots, N_\ell)$.
Then $||X_{M_{\ell+1}}-X_{M_\ell}|| \le 2^{-\ell}$.
But then
\[
\E|X_{M_{\ell+1}}-X_{M_\ell}| \le ||X_{M_{\ell+1}}-X_{M_\ell}|| \le 2^{-\ell}.
\]
Hence
\[
\sum_{\ell=1}^\infty \E|X_{M_{\ell+1}}-X_{M_\ell}| \le 1,
\]
and, by Fubini's theorem,
\[
\E \sum_{\ell=1}^\infty|X_{M_{\ell+1}}-X_{M_\ell}| < \infty.
\]
Therefore, the random variable $sum_{\ell=1}^\infty|X_{M_{\ell+1}}-X_{M_\ell}|$
is finite with probability $1$. Put it otherwise, there is a set $A \in \FF$,
with $\Pr(A)=0$, such that
\[
\sum_{\ell=1}^\infty |X_{M_{\ell+1}}(\omega)-X_{M_\ell}(\omega)| < \infty,
\quad \omega \in A^c.
\]
This means that
\[
\lim_{n \to \infty} \sum_{\ell=1}^{n-1} 
(X_{M_{\ell+1}}(\omega)-X_{M_\ell}(\omega)) \text{ exists for all $\omega \in A^c$}.
\]
But the sum is just $X_{M_n}(\omega) - X_{M_1}(\omega)$. We have thus
proved that for all $\omega \in A^c$ there is $X(\omega)$ such that
$X_{M_n}(\omega) \to X(\omega)$ as $n \to \infty$. Since this
is a limit, the function $X$ is a random variable.
Fix $\ell$ and use \eqref{kosher} again with $m \ge M_\ell$,
$n = M_r$, for $r \ge \ell$:
\[
\E|X_m-X_{M_r}|^2 \le 4^{-\ell}, \quad m \ge M_\ell, \quad r \ge \ell.
\]
By Fatou's lemma,  for all $m \ge M_\ell$,
\[
\E|X_m -X|^2 =
\E \liminf_{r \to \infty} |X_m-X_{M_r}|^2
\le \liminf_{r \to \infty} \E |X_m-X_{M_r}|^2 \le 2^{-\ell}.
\]
Since $||X_m-X|| \ge ||X|| - ||X_m||$, we have $||X|| \le ||X_m||+2^{\ell} 
< \infty$, hence $X \in L^2(\Omega, \FF, \Pr)$. Also, $\lim_{m\to \infty}
||X_m-X|| = 0$, as required.
\end{proof}





\section{Conditioning}
%We warn the reader that this section is quite informal. In other
%words, we will not prove anything, because, without actually
%defining the concepts properly, we cannot prove anything at all.
%
%The proofs and justifications will be given in Chapter 8.

\subsection{Na\"ive conditioning}
Na\"ive conditioning was defined in \fbox{2.1}. Namely, if
$(\Omega, \FF, \Pr)$ is a probability space and $B \in \FF$,
$\Pr(B) \not = 0$, we let
\[
\Pr(A | B) = \Pr(AB)/\Pr(B), \quad A \in \FF,
\]
be a new probability, called $\Pr$ conditional on $B$. We
easily see that $(\Omega, \FF, \Pr(\cdot|B))$ is
a new probability space.

The problem is that, in many cases, we want to condition
with respect to an event $B$ that has probability zero.
This can be done. Loosely speaking, what saves us is the fact that if $\Pr(B)=0$
then $\Pr(AB)=0$ as well. 

We can use many methods for defining conditioning in a more general
sense. We adopt a geometric approach.
In Chapter 8 you will see another approach.


\subsection{Geometry}
Consider the Euclidean space $\R^d$.
Let $\G$ be a linear subspace of it.
Let $||x-y||$ stand for the Euclidean distance between $x, y \in \R^d$, i.e.
\[
||x-y|| := \sqrt{(x_1-y_1)^2 + \cdots + (x_d-y_d)^2},
\]
and
\[
\langle x, y \rangle := x_1 y_1 + \cdots + x_d y_d.
\]
Thus $\langle x, y \rangle / ||x||~ ||y||$ is the
cosine of the angle between $x$ and $y$.
We wish to project an $x \in \R^d$ onto $\G$:
\begin{lemma}
\label{proj}
Given any $x \in \R^d$ there is a unique $\xx \in \G$
such that
\[
||x-\xx|| = \min_{y \in \G} ||x-y||.
\]
\end{lemma}
If we think geometrically, the answer is obvious: this $\xx$ is such that
$x-\xx$ is orthogonal to $\G$; in other words, the angle between $x-\xx$
and any $y \in \G$ is a right angle, i.e.\ its cosine is zero:
\[
\langle x- \xx, y \rangle = 0, \quad y \in \G.
\]
\begin{center}
\epsfig{file=figs/proj.eps,width=5cm}
\end{center}
Equivalently,
\begin{equation}
\label{xx}
\langle \xx, y \rangle = \langle x, y \rangle, \quad y \in \G.
\end{equation}
Since $\G$ is a linear space, \eqref{xx} defines $\xx$ uniquely.
To see this directly, assume that there are two elements $\xx, \xx' \in \G$
satisfying \eqref{xx}. Then $\langle \xx, y \rangle = \langle \xx', y \rangle$
for all $y \in \G$. Thus,
$\langle \xx-\xx', y \rangle = 0$,
for all $y \in \G$.
In particular, for $y = \xx-\xx'$, we have 
$\langle \xx-\xx',\xx-\xx' \rangle = 0$, which immediately gives $\xx=\xx'$.

\no{\bf Proof of Lemma \ref{proj}:}
Define (uniquely) $\xx \in \G$ by \eqref{xx}.  
Obviously,
\[
||\xx-y||^2 = \langle \xx-y, \xx-y \rangle \ge 0,
\quad y \in \G.
\]
We have
\begin{align*}
0 \le \langle \xx-y, \xx-y \rangle 
&= ||\xx||^2 + ||y||^2 - 2 \langle \xx, y \rangle
\\
&=  ||\xx||^2 + ||y||^2  - \langle x, y \rangle - \langle \xx, y \rangle,
\quad y \in \G,
\end{align*}
where we used \eqref{xx}. We now use two things. First,
\[
||x-y||^2 = ||x||^2 + ||y||^2 + 2 \langle x, y \rangle,
\]
and second,
\[
||x||^2 = ||(x-\xx)+\xx||^2 = ||x-\xx||^2 + ||\xx||^2 + 
2 \langle x-\xx, x \rangle = ||x-\xx||^2 + ||\xx||^2,
\]
because $\langle x-\xx, x \rangle=0$, by \eqref{xx}.
Combining the last two displays our inequality becomes
\[
0 \le ||x-y||^2 - ||x-\xx||^2, \quad y \in \G,
\]
which is what we want.
\qed

Notation: We will write 
\[
\xx = \proj (x | \G),
\]
to remind ourselves that $\xx$ is obtained by projecting  $x$ onto $\GG$.

\begin{exe}
Let $\H$ be a linear subspace of $\G$. Then
\[
\proj\big( \proj(x \mid \G) \mid \H\big) = \proj( x \mid \H).
\]
(This should be geometrically `obvious': it is an exercise in
right angles.)
\end{exe}



%We wish to define conditional probability of given a random variable $X$.
%Suppose, in the simplest case, that $X$ takes only two values, $0$, $1$,
%say. Equivalently, $X = \1_B$ for some $B \in \FF$. Whatever
%$\Pr(A |X)$ is it should be such that knowledge of $X$ implies
%knowledge of $\Pr(A|X)$. In other words, $\Pr(A|X)$ should be
%a (measurable) function of $X$. Since $X$ takes only two values we
%have
%\[
%\Pr(A|X) = c_0(A) \1(X=0) + c_1(A) \1(X=1).
%\]
%Multiply both sides by $\1(X=0)$ to get:
%\[
%\Pr(A|X) \1(X=0) = c_0(A) \1(X=0).
%\]
%Now take expectation to get:
%\[
%\E [ \Pr(A|X) \1(X=0) ] = c_0(A) \Pr(X=0).
%\]
%On the other hand, it is reasonable to
%\begin{quote}
%interpret the value of $\Pr(A|X)$ at $X=0$ as the
%na\"ive conditional probability $\Pr(A|X=0)$.
%\end{quote}
%Thus, $\Pr(A|X)$ is a random variable that takes value $\Pr(A|X=0)$
%on $\{X=0\}$ and 

\subsection{Conditional probability}
Suppose now that $\GG\subset \FF$ is a $\sigma$-field. Then
$L^2(\Omega, \GG, \Pr)$ is a linear subspace of $L^2(\Omega, \FF, \Pr)$.
By analogy to the geometric picture above, given $X \in L^2(\Omega, \FF, \Pr)$,
we wish to define $\XX \in L^2(\Omega, \GG, \Pr)$ such that
\[
||X- \XX|| = \min_{Y \in  L^2(\Omega, \GG, \Pr)} ||X-Y||.
\]
Owing to the structure of $L^2(\Omega, \GG, \Pr)$, this can be done:
\begin{theorem}
Let $\GG \subset \FF$ be a $\sigma$-field.
Given $X \in L^2(\Omega, \FF, \Pr)$,
there exists $\XX \in  L^2(\Omega, \GG, \Pr)$
such that one of the following two equivalent statements holds:
\begin{itemize}
\item[(i)] 
\begin{equation}
\label{XXinf}
||X-\XX|| = \inf_{Y \in  L^2(\Omega, \GG, \Pr)} ||X-Y||.
\end{equation}
\item[(ii)] 
\begin{equation}
\label{XX}
\E X Y = \E \XX Y, \quad \text{ for all } Y \in  L^2(\Omega, \GG, \Pr).
\end{equation}
\end{itemize}
Furthermore, $\XX$ is almost surely unique, in the sense that if
$\XX' \in  L^2(\Omega, \GG, \Pr)$ satisfies (i) or (ii) then 
$\Pr( \XX = \XX')=1$.
\end{theorem}

\no{\bf Proof [sketch]:}
We only need to prove existence of such an $\XX$. The rest of the
proof is as in the previous section.
Existence is guaranteed by Lemma \ref{kosher}. Indeed, by the
definition of $\inf$, we can choose $Y_n \in L^2(\Omega, \GG, \Pr)$
such that $||X-Y_n||$ converges to the infimum in \eqref{XXinf}.
It is easy to see that $\sup_{m,n \ge N}||Y_n-Y_m|| \to 0$
as $N \to \infty$, therefore, by Lemma \ref{kosher},
we have an $\XX \in L^2(\Omega, \GG, \Pr)$ such that
$||Y_n - \XX|| \to 0$ as $n \to \infty$.
This $\XX$ does the job.
\qed

We use the following notation:
\[
\XX = \E_\Pr (X | \GG).
\]
The notation reminds us that $\XX$ depends both on $\GG$ and on $\Pr$.
If $\Pr$ is implicitly understood then we just write $\XX = \E (X | \GG)$.

The next exercise justifies using the symbol $\E$ for this projection.
Indeed, if the $\sigma$-field $\GG$ is the smallest possible,
then the projection is a constant, the expectation of $X$:
\begin{exe}
Show that $\E(X| \{\varnothing, \Omega\}) = \E X$.
(Hint: $\E(X-t)^2$ is minimised by $t=\E X$.)
\end{exe}

What happens if $X$ is $\GG$ measurable? 
\begin{exe}
If $X \in L^2(\Omega, \GG, \Pr)$ then $\E(X| \GG) = X$.
\end{exe}

We can also show the double projection property:
\begin{exe}
If $\HH \subset \GG \subset \FF$ are all $\sigma$-fields then
\[
\E(\E(X \mid \GG) \mid \HH) = \E(X \mid \HH).
\]
\end{exe}

Suppose now that $A \in \FF$. Then we define
\[
\Pr(A \mid \GG) := \E(\1_A \mid \GG),
\]
and call this conditional probability of the event $A$ given
the $\sigma$-field $\GG$. By definition, for each $A \in \FF$,
the conditional probability $\Pr(A \mid \GG)$ is a random variable,
specifically it is $\GG$-measurable. 
Also, by linearity, if $A_1 A_2 = \varnothing$,
\[
\Pr(A_1 \cup A_2 | \GG) = \Pr(A_1 \mid \GG) + \Pr(A_2 \mid \GG),
\]
except on a set of probability zero.
The question is: Is $\FF \ni A \mapsto \Pr(A \mid \GG)$ a probability
for almost every $\omega \in \Omega$?
The answer is not obvious because $\Pr(A \mid \GG)$ is defined uniquely
up to an event $N_A$ of probability zero.
Since there are uncountably many $A$'s in $\FF$, it is not clear we
can simultaneously define all the random variables $\Pr(A \mid \GG)$
up to an event of probability zero. 
In special cases this can be done.

\subsection{Conditional law}
Here is one such special case: Let $X, Y$ be random variables
on $(\Omega, \FF, \Pr)$ with  finite second moments. We define
\[
\Pr(X \in B \mid Y) := \Pr(X^{-1}(B) \mid \sigma(Y)), \quad B \in \BB.
\]
While we can certainly do this rigorously for each fixed $B \in \BB$,
it is not immediate that for each $\omega \in \Omega$, this
is a probability in $B$.
It can be shown that it actually is, in the sense that we can choose
$\Pr(X \in B \mid Y)$ so that it is a probability as a function of $B$
and simultaneously a measurable function of $Y$.
We call this object conditional law of $X$ given $Y$.

The conditional distribution function of $X$ given $Y$ is defined
as
\[
\Pr(X \le x \mid Y).
\]
To be honest with the definitions, we must make sure they
reduce to the usual na\"ive ones from elementary probability.
We consider two cases.

\subsubsection{Case 1: $(X,Y)$ is absolutely continuous}
\begin{lemma}
Suppose that $(X,Y)$ is absolutely continuous with joint density
$f(x,y)$. Let $f_2(y) = \int_\R f(x,y) dx$ be the density of $Y$.
Define the conditional density of $X$ given $Y$ by
\[
f_{X|Y}(x|y) := 
\begin{cases}
\displaystyle
\frac{f(x,y)}{f_2(y)},& \quad \text{if } f_2(y) \not = 0,
\\
0,& \quad \text{otherwise}.
\end{cases}
\]
For $B \in \BB$, let
\[
g_B(y) := \int_B f_{X|Y}(x|y) dx.
\]
Then
\[
P(X \in B | Y) = g_B(Y),
\]
for all $\omega$ except on a set of probability zero.
\end{lemma}
\begin{proof}
We need to show that (see \eqref{XX})
\[
\E \1(X \in B) W = \E g_B(Y) W,
\]
for all $W \in L^2(\Omega, \sigma(Y), \Pr)$.
It is enough to show this for al, $W$ of the form $W=\1(Y \in C)$,
$C \in \BB$:
\[
\E \1(X \in B) \1(Y \in C) = \E g_B(Y) \1(Y \in C).
\]
But the left hand side equals
\[
\int_{\R^2} \1_B(x) \1_C(y) f_{X,Y} dx dy.
\]
The right hand side equals
\[
\int_R g_B(y) \1_C(y) dy.
\]
These two quantities are the same, by Fubini's theorem.
\end{proof}


\subsubsection{Case 2: $(X,Y)$ is discrete}
Suppose that $(X,Y)$ takes values in a discrete set $S_1 \times S_2$.
As usual, define its probability mass function and marginal mass functions by
\[
p(x,y) := \Pr((X,Y)=(x,y)),
\quad
p_1(x) := \Pr(X=x),
\quad
p_2(y) := \Pr(Y=y),
\quad
(x,y) \in S_1 \times S_2.
\]
We then have a simple formula for the conditional law of $X$ given $Y$,
precisely the one we expect:
\begin{lemma}
Let $(X,Y)$ be a random variable on $(\Omega, \FF, \Pr)$
with values in the discrete set $(S_1\times S_2, 2^{S_1\times S_2})$.
Define the conditional probability mass function of $X$ given $Y$ by
\[
p_{X|Y}(x|y) := 
\begin{cases}
\displaystyle
\frac{p(x,y)}{p_2(y)},& \quad \text{if } p_2(y) \not = 0,
\\
0,& \quad \text{otherwise}.
\end{cases}
\]
Let $\Pr(X=x | Y)$ be defined as the projection of $\1(X=x)$ onto
$L^2(\Omega, \sigma(Y), \Pr)$.
Then\footnote{
The notation $p_{X|Y}$ is terrible. We only use it out of some respect
to the undergraduate probability courses. The reason that the notation
is terrible is that in the subsript `$X|Y$' in $p_{X|Y}(x | Y)$ plays
a merely cosmetic r\^ole, as opposed to the essential r\^ole played by the
last variable $Y$ inside the parenthesis.
}
\[
\Pr(X=x | Y) = p_{X|Y}(x | Y).
\]
\end{lemma}
\begin{proof}
We need to verify that $p_{X|Y}(x | Y)$ satisfies \eqref{XX}, namely,
\[
\E \1(X=x) W = \E p_{X|Y}(x | Y) W, \quad W \in L^2(\Omega, \sigma(Y), \Pr).
\]
We work with the case where $S_2$ is a finite set, the more general
case being similar. We can then write $Y$ as a finite sum of the form
\[
Y= \sum_y y \1(Y=y)
\]
where the $A_k$ are mutually disjoint with $\Pr(A_k) > 0$.
Any $W$ which is $\sigma(Y)$-measurable is a function  of $Y$, and
so we can take
\[
W = \sum_y g(y) \1(Y=y).
\]
We have
\begin{align*}
\E [p_{X|Y}(x|Y) W] &= \sum_y g(y) \E [p_{X|Y}(x|Y) \1(Y=y)]
\\
&= \sum_y g(y) \E [p_{X|Y}(x|y) \1(Y=y)]
= \sum_y g(y) p_{X|Y}(x|y) \Pr(Y=y).
\end{align*}
If $\Pr(Y=y)=0$ then $p_{X|Y}(x|y)=0$.
Otherwise, $p_{X|Y}(x|y) = p(x,y)/p_2(y)$, and so
\begin{gather*}
\E [p_{X|Y}(x|Y) W] 
= \sum_y g(y) p(x,y)
= \E X W,
\end{gather*}
as required.
\end{proof}



%\section{Lots of independent random variables}



\section{Gaussian variables}
\subsection{The Gaussian law}
The motivation of the Gaussian probability comes from the 
central limit theorem (which, long time ago, was known
as the ``law of errors''). This was stated, without proof, in \fbox{2.3.2}.
We work heuristically in order to motivate the definitions.
Let $S_n = \xi_1+\cdots + \xi_n$
be the sum of $n$ independent indicator (also
known as Bernoulli) random variables $\xi_i$ with $\Pr(\xi_i=1) = p$ for
all $i$. Let $\widehat S_n = S_n - \E S_n$.
Then, as $n \to \infty$, the distribution function of $\widehat S_n/\sqrt{n}$
converges to an absolutely continuous distribution function
with a famous formula.
Let $X$ be a random variable with such a distribution function.
Note that
\[
\frac{\widehat S_{2n}}{\sqrt{n}} = 
\frac{1}{\sqrt{2}} \frac{\widehat S_n}{\sqrt{n}} +
\frac{1}{\sqrt{2}} \frac{\widehat S'_n}{\sqrt{n}},
\]
where $\widehat S'_n = \xi_{n+1} + \cdots + \xi_{2n}$ is
a random variable with the same law as $\widehat S_n$.
So the distribution of $\frac{\widehat S'_n}{\sqrt{n}}$ will
also converge to the distribution of $X$. Moreover,
$\widehat S'_n$, $\widehat S_n$ are independent.
Therefore, if $X_1, X_2$ are independent random variables
with the same law as $X$, then we expect that
\[
X = \frac{X_1+X_2}{\sqrt{2}}.
\]
Even if we do not know what this famous distribution is, it
should be such that this ``addition law'' holds. {From} this,
we can discover its density. One way to do that is by imposing the
extra assumption (which is not necessary) that the generating
function of $X$ exists for all $\theta$: $M(\theta) = \E e^{\theta X}$.
Then
\[
M(\theta) = M(\theta/\sqrt{2})^2.
\]
Letting $\theta = \sqrt{\eta}$ and taking logarithms, we have
\[
\log M(\sqrt{\eta}) = 2 \log M(\sqrt{\eta/2}).
\]
So, if we temporarily let $m(\eta) = \log M(\sqrt(\eta))$
we have
\[
m(\eta) = 2 m(\eta/2).
\]
So $m(0)=0$ and
with some work, we can actually find that the only 
continuous function satisfying the latter is linear: $m(\eta) = c \eta$.
(This should be geometrically obvious.)
Hence
\[
M(\theta) = e^{c \theta^2}.
\]
{From} Lemma \ref{mmm} we know that the moments of $X$
are given by the derivatives of $M$ at $0$. We find
\[
M'(0) =0, \quad M''(0) = 2c.
\]
So $\E X=0$ (as it should), while $\E X^2 = 2c$.
So $c > 0$. Since $\E X=0$, the second moment is the variance
and we customarily denote it by $\sigma^2$. We arrive at
\[
M(\theta) = e^{\frac{1}{2} \sigma^2 \theta^2}.
\]
We know that there is only one probability distribution with
a given moment generating function. Instead of trying to figure out
which one it is, let us reveal the result and then just verify
that it is correct. We claim that the probability distribution corresponding 
to the last $M$ is absolutely continuous with density
\[
f(x) = C e^{-x^2/2\sigma^2}.
\]
Here, $C$ is such that $\int_\R f(x) dx = 1$.
This is the famous normal or Gaussian density with mean $0$ and
variance $\sigma^2$. It is called standard if $\sigma^2=1$.
\begin{exe}
Show that $\int_{-\infty}^\infty e^{\theta x} f(x) dx
=  e^{\frac{1}{2} \sigma^2 \theta^2}$.
(Hint: Complete the square and use the definition of $C$.)
\end{exe}
Now, to find $C$ is a very important thing. It is based on the following:
\begin{lemma}
\[
\int_\R e^{-x^2} dx = \sqrt{\pi}.
\]
(Liouville said that a Mathematician is someone for whom this
integral is obvious.)
\end{lemma}
\begin{exe}
Use Fubini's theorem to write
$\left(\int_\R e^{-x^2} dx\right)^2 =
\int_{\R^2} e^{-x^2-y^2} dx dy$ and do the latter
integral using polar co\"ordinates.
\end{exe}
Using this we find that 
\[
C= \frac{1}{\sqrt{2\pi\sigma^2}}.
\]
Therefore, the standard normal density is
\[
\phi(x)
= \frac{1}{\sqrt{2\pi}} e^{-x^2/2}.
\]
We write $\NN(0,1)$ for the law of a random variable $X$ with standard normal
density. We write $\NN(\mu, \sigma^2)$ for the
law of $\sigma X + \mu$.

\begin{exe}
Show that a density for $\NN(\mu,\sigma^2)$ is
\[
\frac{1}{\sqrt{2\pi\sigma^2}}
\exp\left\{ - \frac{(x-\mu)^2 }{2\sigma^2} \right\}.
\]
\end{exe}

\begin{exe}
Show that if $X_i, i=1, \ldots, d$ are independent
and $X_i$ having law $\NN(\mu_i, \sigma_i^2)$ then
$\sum_{i=1}^d X_i$ has law $\NN(\sum_i \mu_i, \sum_i \sigma_i^2)$.
Therefore linear combinations of independent normal
variables are normal.
\end{exe}



\subsection{The multidimensional Gaussian random variable}
We now pass on to defining a Gaussian (or normal) variable in
$\R^d$ (i.e.\ a random vector). 
\begin{quote}
We say that $(X_1, \ldots, X_d)$
is Gaussian in $\R^d$ if, for all $a_1, \ldots, a_d \in \R$,
the random variable $a_1 X_1 + \cdots + a_d X_d$ is normal.
\end{quote}
The next lemma shows what the moment generating function
of a normal vector is:
\begin{lemma}
If $(X_1, \ldots, X_d)$ is Gaussian vector with
\[
\mu_j = \E X_j, \quad r_{jk} = \cov(X_j, X_k),
\]
then
\[
\E \exp \sum_{j=1}^d \theta_j X_j
= \exp \left\{
\sum_{j=1}^d \mu_j \theta_j 
+ \frac{1}{2} \sum_{j=1}^d \sum_{k=1}^d r_{jk} \theta_j \theta_k \right\}.
\]
\end{lemma}
\begin{proof}
By definition $\sum_{j=1}^d \theta_j X_j$ should be normal,
i.e.\ have a law $\NN(\mu, \sigma^2)$, for some $\mu, \sigma^2$.
We have
\[
\mu = \E \sum_{j=1}^d \theta_j X_j = \sum_{j=1}^d \mu_j \theta_j,
\quad
\sigma^2 = \cov \sum_{j=1}^d \theta_j X_j 
= \sum_{j=1}^d\sum_{k=1}^d \theta_j \theta_k \cov(X_j, X_k).
\]
\end{proof}

Since the moment generating function of a Gaussian vector
is the exponential of a quadratic form, there is no better way
to express it other than using Linear Algebra. To this end,
we think of the elements $x$ of  $\R^d$  as column vectors.
We use $x'$ to denote transposition, i.e.\ the corresponding row
when $x$ is a column. And, of course, $(x')' = x$.
Consider the mean (column) vector
\[
\mu = (\mu_1, \ldots, \mu_d)'
\]
and the symmetric covariance matrix
\[
R= [r_{jk}].
\]
Write also $X$ for the column with entries $X_1, \ldots, X_d$.
We then have
\[
\E e^{\theta' X} = 
\exp \left\{ \theta' \mu + \frac{1}{2} \theta' R \theta \right\}.
\]
This uniquely defines the law of $(X_1, \ldots, X_d)$.
This law is denoted by $\NN(\mu, R)$, where
$\mu$ is the mean vector and $R$ the covariance matrix.



\begin{lemma}
A Gaussian vector $(X_1, \ldots, X_d)$ is absolutely continuous
if and only if $R$ is invertible. In this case, its
density is given by
\[
f(x) = \frac{1}{\sqrt{(2\pi)^d\det(R)}} \exp\left(-\frac{1}{2}(x-\mu)'R^{-1}(x-\mu)\right)\,.
\]
\end{lemma}
\begin{proof}
Assume $\mu=0$, to ease notation.
Assume $R$ is invertible.
It is easily seen that 
\[
R=\E(XX')
\]
where $X X'$ is a $d \times d$ matrix and $\E(X X')$ is the matrix
formed by taking the expectations of the entries of $X X'$.
This $R$ has two important properties: \\
(i) it is symmetric (obviously); \\
(ii) it is positive semi-definite, i.e.\ the quadratic form
\[
u'Ru=\sum_k\sum_\ell R_{k\ell}u_k u_\ell \ge 0
\]
for all values of
the variables, positive or negative. The reason for the latter is that
$u'Ru $ is the expectation of a non-negative quantity:
\[
u'Ru=u'\E XX'u=\E(X'u)'(X'u) = \E(X'u)^2 \ge 0.
\]
Standard linear algebra
shows that $R$ has exactly $d$ (counting multiplicities) non-negative eigenvalues.
(In fact, they are strictly positive,
due to the invertibility of $R$ which is tantamount to
$\det(R) \ne 0$). 
Furthermore, the eigenvectors can be chosen to be orthonormal.
Letting $U$ be the matrix whose columns are these $d$ orthonormal eigenvectors
and $\Lambda$ the diagonal matrix with the eigenvalues in its diagonal,
we have 
\[
RU = U \Lambda, 
\]
from the very definition of the eigenvectors.
Now 
\[
U'=U^{-1},
\]
hence 
\[
R=U \Lambda U' = U \Lambda^{1/2} \Lambda^{1/2} U' =
P P',
\]
with 
\[
P=U \Lambda^{1/2}.
\]
The matrix $P$ is non-singular and is called
the square root of $R$. We now define new random variables $Z$ by 
\[
X = P Z\,.
\]
The thing to observe is that the covariance matrix of $Z$ is
\[
\cov(Z) = \E ZZ' = \E P^{-1}XX'P'^{-1}=P^{-1}R'P'^{-1}=P^{-1}PP'P'^{-1}=I,
\]
$I$ being the identity matrix. Thus 
\[
\E e^{\theta'Z} = e^{\theta'\theta/2}=
\prod_{j=1}^d e^{\theta_j^2/2} = \prod_{j=1}^d \E e^{\theta_jZ_j},
\]
implying that the components of $Z$ are independent standard normal.
Hence the density $g$ of $Z$ is product:
\[
g(z) = \prod_j \frac{1}{\sqrt{2\pi}} e^{-z_j^2/2}.
\]
Now $X=PZ$, hence its density $f$ is computed easily
by 
\[
f(x) = g(P^{-1}x)/|\det(P)|,
\]
which yields the desired formula.
\end{proof}




If $R$ has determinant zero then it is possible to ``reduce the dimension''
of the random vector $X$ so that the density exists.
In fact,
\begin{lemma}
The support of $X$ is the range of its covariance matrix $R$.
\end{lemma}
\begin{proof}
Suppose that $R$ has rank $r$. Then it has $d-r$ eigenvalues at zero,
so that the matrix $\Lambda$ consists of a $d-r$ size block of zeros and 
the remaining non-zero eigenvalues. Hence now $R = PP'$,
where $P$ is a $d\times r$ matrix with rank $r$. 
We try again to find $Z$ so that 
\[
X=PZ,
\]
where $Z$ is an $r$-dimensional random vector with density.
If we manage to do this we will finish, since the range of $P$ is
the range of $R$. Observing that $P'P$ is an $r\times r$ non-singular matrix,
we pre-multiply by it to get $P'PZ = P'X$, hence $Z=(P'P)^{-1}P'X$.
So if we define $Z$ this way, we see that 
\[
\E ZZ'=
(P'P)^{-1}P'RP(P'P)^{-1} =
(P'P)^{-1}P'PP'P(P'P)^{-1}=I,
\]
i.e.\ $Z$ is a collection of $r$ independent
standard normal variables.
The formula for $Z$ is the formula that solves a full-rank over-estimated
linear system. We usually write $Z = P^+ X$ and call $P^+$ the pseudo-inverse of $P$.
It remains to show that every linear function of $X$ is a linear function of $Z$.
Let \[
F=\lambda'Xa \quad, G=\lambda'PZ
\]
with $Z=P^+X$.
Consider 
\[
F-G=\lambda'(X-PZ).
\]
Then 
\[
\E (F-G)^2 = \E \lambda'(X-PZ)(X'-Z'P')\lambda
=\E \lambda'(XX'-XZ'P'-PZX'+PZZ'P')\lambda.
\]
But 
\[
\E ZX'=(P'P)^{-1}P'\E XX'=(P'P)^{-1}P'PP'=P'.
\]
So 
\[
\E (F-G)^2 = \lambda'(PP'-PP'-PP'+PP')\lambda=0.
\]
\end{proof}

Terminology: If $X$ has law $\NN(0,R)$ with $R$ having rank $r$
then $\sum_j X_j^2$ is called $\chi^2$ with $r$ degrees of freedom.


\subsection{Conditional Gaussian law}
If it appears that we've done a lot of Linear Algebra, then this
is because it is so: 
Dealing with Gaussian random variables (and processes!) 
is mostly dealing with Linear Algebra (or Linear Analysis!).

Without proof, we mention the following:
\begin{lemma}
Let $(X; Y_1, \ldots, Y_d)$ be a Gaussian random variable in $\R^{1+d}$.
Then the conditional law $\Pr(X \in \cdot | Y_1, \ldots, Y_d)$ is
normal with mean $\E(X | Y_1, \ldots, Y_d)$ and deterministic covariance matrix.
Moreover, $\E(X | Y_1, \ldots, Y_d)$ is a linear function of 
$Y_1, \ldots, Y_d)$.
\end{lemma}

\begin{exe}
Let $X, Y$ be independent standard Gaussian variables.
Based on the last part of the lemma above, compute
$\E(X+2Y | 3X-4Y)$.
(Hint: Make sure that \eqref{XX} is satisfied.)
\end{exe}


\end{unit}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{5}{Important special distributions }
% SYLLABUS:
%5.  Important special distributions.                                    TK
%      Binomial,	DONE
% Poisson,	DONE
% geometric,	DONE
% uniform, DONE IN CHAPTER 3
% exponential DONE
% and normal  distributions: DONE IN CHAPTER 3
% definitions, properties and the relations between them.	DONE


\section{Outline}
We discuss several special random variables,
and simple relationships between their distributions.


\section{Binomial, Poisson, and multinomial}
Consider the coin tossing experiment, i.e.\ consider a sequence
$\xi_1, \xi_2, \ldots$ of i.i.d.\ random variables with
\[
\Pr (\xi_1=1)=p, \quad \Pr(\xi_1=0)=1-p.
\]
The law of 
\[
S_n = \xi_1 + \cdots + \xi_n
\]
is called Binomial with parameters $n$ and $p$.
{From} this we have
\[
\E S_n = n p, \quad \var S_n = n \var \xi_1 = np(1-p),
\]
and, since $\xi_{n+1} + \xi_{n+m}$ is Binomial with parameters
$m$ and $p$, and independent of $S_n$, we have that the sum
of two independent Binomial random variables with the same $p$
is again Binomial.
We also have
\[
\Pr(S_n=k) = \binom{n}{k} p^k (1-p)^{n-k}, \quad
k=0,1,\ldots, n,
\]
and, from the Binomial theorem,
\[
\E e^{\theta S_n} = (p e^\theta + 1-p)^n.
\]
\begin{exe}
Compute the moment generating function of $n^{-1/2}(S_n - \E S_n)$
and show that, as $n \to \infty$, it converges to the
moment generating function of a Gaussian random variable.
\end{exe}
\begin{exe}
Use Chernoff's inequality to estimate $\Pr(S_n > n(p+x))$
for $x > 0$.
\end{exe}

By letting $p$ vary with $n$ and taking limits we obtain a
different fundamental law, the Poisson  law.
Specifically,
\begin{lemma}
If $p_n = \frac{\lambda}{n} + o(1/n)$, as $n \to \infty$, then
\[
\Pr(S_n=k) \to \frac{\lambda^k}{k!} e^{-\lambda},
\]
for all $k = 0,1,2, \ldots$.
\end{lemma}
\begin{proof}
Use Stirling's formula.
\end{proof}

This is the Poisson law with parameter $\lambda$. The Poisson law
is fundamental when, roughly speaking,
we deal with independent rare events.

Let $X$ be a Poisson random variable. Then
We have
\[
\E e^{\theta X} = \sum_{k=0}^\infty \frac{(\lambda e^{\theta})^k}{k!} 
e^{-\lambda} = e^{\lambda (e^\theta-1)} .
\]
Differentiating a couple of times, we find
\[
\E X = \lambda, \quad \var X = \lambda.
\]
Furthermore,
\begin{lemma}
If $X_1, X_2, \ldots$ are independent Poisson random variables
with parameters $\lambda_1, \lambda_2, \ldots$ such that
$\sum \lambda_k < \infty$ then $\sum_k X_k$ is Poisson
with parameter $\sum_k \lambda_k$.
\end{lemma}
\begin{proof}
We prove this for a finite number $n$ of random variables (which
is enough by the way we construct a probability on
an infinite product). The moment generating function
of $X_1 + \ldots + X_n$ is
\[
\prod_{k=1}^n e^{\lambda_k (e^\theta-1)}
= e^{(e^\theta-1) \sum_{k=1}^n \lambda_k}
\]
and this is the moment generating function of a Poisson law
with parameter $\sum_k \lambda_k$.
\end{proof}

Next we consider conditional probabilities:
\begin{lemma}
Suppose that $X_1, X_2$ are independent Poisson with parameters
$\lambda_1, \lambda_2$. Then, conditional on $X_1+X_2=n$, we
have that $X_1$ is Binomial with parameters $n$, 
$\lambda_1/(\lambda_1+\lambda_2)$.
\end{lemma}
\begin{proof}
Elementary conditioning: For $0 \le k \le n$,
\begin{gather*}
\Pr(X_1 = k | X_1+X_2=n) =
\frac{\Pr(X_1=k, X_2=n-k)}{\Pr(X_1+X_2=n)}\\
= \frac{\displaystyle \frac{\lambda_1^k}{k!} e^{-\lambda_1}
~ \frac{\lambda_2^{n-k}}{(n-k)!} e^{-\lambda_2}}
{\displaystyle \frac{(\lambda_1+\lambda_2)^n}{n!} e^{-\lambda_1-\lambda_2}}
\\
= \binom{n}{k} \left(\frac{\lambda_1}{\lambda_1+\lambda_2}\right)^k
\left(\frac{\lambda_2}{\lambda_1+\lambda_2}\right)^{n-k}.
\end{gather*}
\end{proof}

Generalising this, we have:
\begin{lemma}
Suppose that $X_1, X_2, \ldots, X_d$ are independent Poisson
with parameters $\lambda_1, \lambda_2, \ldots, \lambda_d$,
respectively. 
Then, conditionally on 
$\sum_k X_k = n$, the random vector $(X_1, \ldots, X_d)$ has
law given by
\[
\Pr(X_1=n_1, \ldots, X_d = n_d \mid \sum_k X_k = n)
= \binom{n}{n_1, \ldots, n_d}
\left(\frac{\lambda_1}{\lambda}\right)^{n_1}
\cdots
\left(\frac{\lambda_d}{\lambda}\right)^{n_d},
\]
where $(n_1, \ldots, n_d)$ are nonnegative integers with sum equal to $n$,
and $\lambda=\sum_k \lambda_k$,
and where
\[
\binom{n}{n_1, \ldots, n_d} = \frac{n!}{n_1! \cdots n_d!}
\]
\end{lemma}
\begin{exe}
Show this.
\end{exe}

The symbol $\displaystyle \binom{n}{n_1, \ldots, n_d}$ 
is the multinomial coefficient
since it appears in the algebraic identity known as multinomial theorem:
\[
(x_1 + \cdots + x_d)^n = \sum_{} \binom{n}{n_1, \ldots, n_d}
x_1^{n_1} \cdots x_d^{n_d}.
\]
The sum is taken over all nonnegative integers
$(n_1, \ldots, n_d)$, with sum equal to $n$.

The random variable $(X_1, \ldots, X_d)$ with values in $\Z^d_+$
is said to have a multinomial distribution with
parameters $d, n, p_1, \ldots, p_d$ (where $p_1+\cdots + p_d=1$, so
one of them is superfluous) if
\[
\Pr(X_1=n_1, \ldots, X_d = n_d) 
= \binom{n}{n_1, \ldots, n_d} p_1^{n_1} \cdots p_d^{n_d},
\]
where $(n_1, \ldots, n_d)$ are nonnegative integers with sum equal to $n$,

Of course, a multinomial distribution with parameters $2, n, p, 1-p$
is a binomial distribution with parameters $n, p$.


\section{Thinning}
Suppose an urn contains $n$ balls. There are $d$ colours available.
Let the colours be denoted by $c_1, c_2, \ldots, c_d$.
To each ball assign colour $c_i$ with probability $p_i$,
independently from ball to ball. Let $S^i_n$ be the number
of balls that have colour $c_i$, $1 \le i \le d$.
It is easy to see that $(S^1_n, \ldots, S^d_n)$ has
a multinomial law:
\[
\Pr(S^1_n = k_1 , \ldots, S^d_n=k_d) =
\binom{n}{k_1, \ldots, k_d} p_1^{k_1} \cdots p_d^{k_d},
\]
where $(k_1, \ldots, k_d)$ are nonnegative integers summing
up to $n$.
Clearly,
\[
S^1_n + \cdots S^d_n = n,
\]
so the random variable $S^1_n, \ldots, S^d_n$ cannot be independent.
The question is:
\begin{quote}
Suppose that the number of balls is itself a random variable, independent
of everything else. Is there a way to choose the law of this random
variable so that the above variables are independent?
\end{quote}
To put the problem in precise mathematical terms, let
$\xi_1, \xi_2, \ldots$ be i.i.d.\ random colours, i.e.\ random
variables taking values in $\{c_1, \ldots, c_d\}$ such that
\[
\Pr(\xi_1 = c_i) = p_i, \quad 1 \le i \le d.
\]
Let
\[
S^i_n := \sum_{k=1}^n \1(\xi_k=c_i).
\]
(In physical terms, $S^i_n$ denotes precisely what we talked about earlier
using a more flowery language.)
Now, independent of the sequence $\xi_1, \xi_2, \ldots$, let $N$
be a random variable with values in $\Z_+$. The problem is
to find its law so that
\[
\text{$S^1_N, \ldots, S^d_N$ are independent random variables. 
\qquad\qquad  ($\star$)}
\]
It turns out that this is a characterising property of the Poisson law.
We will contend ourselves by proving one direction:
\begin{lemma}
If $N$ is Poisson then ($\star$) holds.
Moreover, if $N$ has expectation $\lambda$, then
$S^i_N$ is also Poisson with expectation $\lambda p_i$.
\end{lemma}
\begin{exe}
Prove the last lemma.
\end{exe}



\section{Geometric}
A random variable $X$ with values in $\N$ is geometric if
it has the memoryless property:
\begin{quote}
For each $k \in \N$, the conditional distribution of $X-k$
given $\{X > k\}$ is the same as the distribution of $X$:
\[
\Pr(X-k = n | X > k) = \Pr(X=n).
\]
\end{quote}
Think of $X$ as a random time, e.g.\ the day on which a certain
volcano will erupt. The property above says that if by day $k$
the volcano has not erupted then the remaining time $X-k$ has
the same law as $X$, no matter how large $k$ is.
\begin{lemma}
If $q=\Pr(X>1)$ then 
\[
\Pr(X > k) = q^k, \quad k \in \N
\]
and 
\[
\Pr(X=k) = p q^{k-1},
\]
where $p=1-q$.
\end{lemma}
\begin{proof}
By the property of $X$,
\[
\Pr(X > k+n| X >k) = \Pr(X > n),
\]
for all $k, n$, which means that
\[
\Pr(X>k+1) = \Pr(X>k) \Pr(X>1).
\]
Iterating this, we find
\[
\Pr(X>k) = \Pr(X>1)^k, \quad k = 0,1,\ldots.
\]
\end{proof}

People refer to $X$ as geometric with parameter $p$.
The terminology is not standard because other people refer to $X-1$
(which also has the memoryless property but takes values in
$\Z_+$) as geometric with parameter $q$.
A matter of taste, really.

It is easy to see that
\begin{lemma}
If $X$ is geometric in $\N$ with $\Pr(X=1)=p$ then
\[
\E X = 1/p, \quad \var X = (1-p)/p^2,
\quad 
\E e^{\theta X} = \frac{p e^\theta}{1-(1-p)e^\theta}.
\]
\end{lemma}
\begin{exe}
Do all that.
\end{exe}

A concrete way to get a geometric random variable is
by considering $\xi_1, \xi_2, \ldots$ to be i.i.d.\
with
\[
\Pr(\xi_1=1)=1-\Pr(\xi_1=0)=p
\]
and by letting
\[
X = \inf\{k \ge 1:~ \xi_k=1\}.
\]
We have $\Pr(X< \infty) =1$, so
\[
X = \min\{k\ge 1:~ \xi_k=1\}
\]
and 
\[
\Pr(X > k) = \Pr(\xi_1= \cdots= \xi_{k}=0) = (1-p)^k,
\]
as required.

We have that
\begin{lemma}
If $X_1, X_2, \ldots, X_d$ are independent and geometric
then $X = \min(X_1, \ldots, X_d)$ is geometric.
\end{lemma}
\begin{proof}
\begin{gather*}
\Pr(X > k) = \Pr(X_1 >k, \ldots, X_d > k)\\
= \Pr(X_1 >k) \cdots \Pr(X_d > k) 
\\
= q_1^k \cdots q_d^k =
(q_1\cdots q_d)^k.
\end{gather*}
\end{proof}
\begin{exe}
Let $X, Y$ be independent and geometric.
Show that 
\[
\Pr(X-Y > n | X > Y) = \Pr(X > n),
\]
for all $n$, and interpret the formula.
\end{exe}



\section{Uniform}
We have already seen, in detail, how to construct a uniform
random variable, from first principles. Recall that $U$ is
uniform in the interval $[0,1]$ if $\Pr(U\le x) = x$, $0 \le x \le 1$.
More generally, 
\begin{quote}
$X$ is uniform in $[a,b]$ if, for
all intervals $I$, the probability $\Pr(X \in I)$ is proportional to the 
length of $I$.
\end{quote}
Of course, if $X$ is uniform in $[a,b]$, then $cX+d$
is uniform in the interval with endpoints $ca+d$ and $cb+d$.

Recall that if $F$ is a distribution function 
and $U$ is uniform in $[0,1]$ then $F^{-1}(U)$ is
a random variable with distribution function $F$.

\begin{lemma}
Let $p_1, \ldots, p_d$ be positive numbers adding up to $1$.
Split the interval $[0,1]$ into consecutive intervals $I_1, \ldots, I_d$
of lengths $p_1, \ldots, p_d$, respectively. Let $U_1, \ldots, U_n$
be i.i.d.\ uniform in $[0,1]$. Let
\[
S_n^i = \sum_{k=1}^n \1(U_k \in I_i),
\quad 1 \le i \le d.
\]
Then $(S_n^1, \ldots, S_n^d)$ has a multinomial law.
In particular, $S^i_n$ is Binomial with parameters $n, p_i$.
\end{lemma}
\begin{exe}
Show this last lemma.
\end{exe}
\begin{exe}
Let $U_1, \ldots, U_d$ be i.i.d.\ uniform in $[0,1]$.
Compute the probability $\Pr(U_1 < U_2 < \cdots < U_d)$.
\end{exe}
\begin{exe}
Consider a stick of length $1$ and break it into 3 pieces, by
choosing the two break points at random.
Find the probability that the 3 smaller sticks can be joined to form
a triangle.
\end{exe}
\begin{exe}
Pick a random variable $U_1$ uniform in $[0, 1]$.
Let $U_2$ be the midpoint of the interval $[0, U_1]$ or
of $[U_1, 1]$, with equal probability.
Continue in the same manner and define $U_3$ to be the midpoint
of $[0,U_2]$ or of $[U_2, 1]$, with equal probability.
Show that the $x \mapsto \lim_{n\to \infty}\Pr(U_n \le x)$ 
is continuous but not absolutely so.
\end{exe}


\section{Exponential}
A random variable $T$ with values in $\R_+$ is exponential if it
has the memoryless property:
\begin{quote}
For all $t, s > 0$,
\[
\Pr(T-t > s | T > t)= \Pr(T > s).
\]
\end{quote}
\begin{lemma}
If $T$ is exponential then there is $\lambda > 0$ such that
\[
\Pr(T > t) = e^{-\lambda t}, \quad t \ge 0.
\]
\end{lemma}
\begin{proof}
Implicit in the definition is that $\Pr(T > t) > 0$ for all $t$.
Hence $\alpha := \Pr(T>1) \in (0,1)$.
We have
\[
\Pr(T > t+s) = \Pr(T>t) \Pr(T> s)
\]
for all $t,s$.
Using this and induction, we have that, for all $n \in \N$,
\[
\Pr(T > nt) = \Pr(T>t)^n.
\]
This gives that, for all $m \in \N$,
\[
\Pr(T > 1 = m(1/m)) = \Pr(T > 1/m)^m
\]
and so $\Pr(T> 1/m) = \Pr(T>1)^{1/m}$.
Letting $t=1/m$ in the pre-last display,
we have
\[
\Pr(T > n/m) = \alpha^{n/m}.
\]
Now, for $t>0$, let $q_1> q_2> \ldots$ be
rational numbers with $\inf\{q_1, q_2, \ldots\} = t$.
Then 
\[
\Pr(T > t) = \Pr(\cup_k \{T > q_k\})
= \sup_k \Pr(T>q_k) = \sup_k \alpha^{q_k}
= \alpha^{\inf_k q_k} = \alpha^t.
\]
Since $\alpha < 1$, we have $\lambda := -\log \alpha > 0$.
\end{proof}

We say that $T$ is exponential with parameter (rate) $\lambda$.

It is easy to see that
\begin{lemma}
If $T$ is exponential with rate $\lambda$ then $T$ has
density
\[
f(t) = \lambda e^{-\lambda t}, \quad t \ge 0.
\]
Also,
\[
\E e^{\theta T} = \frac{\lambda}{\lambda-\theta},
\]
defined for all $\theta < \lambda$,
and
\[
\E T = 1/\lambda, \quad
\var T = 1/\lambda^2.
\]
\end{lemma}
\begin{proof}
Note that 
\[
\int_0^t f(s) ds = 1-e^{-\lambda t},
\]
showing that $f$ is a density for $T$.
The rest are trivial.
\end{proof}

\begin{lemma}
Let $T_1, T_2, \ldots, T_d$ be independent  exponential random variables
with parameters $\lambda_1, \lambda_2, \ldots, \lambda_d$, respectively.
Then $\min(T_1, \ldots, T_d)$ is exponential with parameter
$\lambda_1+\cdots+\lambda_d$.
\end{lemma}
\begin{proof}
\[
\Pr(\min(T_1, \ldots, T_d)>t) = \Pr(T_1>t) \cdots \Pr(T_d > t).
\]
\end{proof}

Whereas an exponential is the natural analogue of a geometric,
in that they are both memoryless, the former also enjoys the important
scaling property:
\begin{quote}
If $T$ is exponential with rate $\lambda$ then, for any $c > 0$,
 $cT$ is exponential with rate $\lambda/c$,
\end{quote}
and this is obvious.

\begin{exe}
Let $T_1, T_2, \ldots, T_d$ be independent  exponential random variables
all with rate $1$. Show that 
\[
\text{law of } \max(T_1, \ldots, T_d) =
\text{ law of } \left(T_1 + \frac{T_2}{2}+ \cdots + \frac{T_d}{d}\right).
\]
\end{exe}

Another relation between geometric and exponential is
the following: Let $p$ be very small. Let $X$ be geometric
with parameter $p$. Consider a scaling of $X$ by $p$, i.e.\ the
random variable $pX$ which takes values $p,2p,3p,\ldots$.
Then the law of $pX$ converges to an exponential law
with rate $1$:
\begin{lemma}[R\'enyi]
For $X$  geometric with parameter $p$,
\[
\lim_{p \to 0} \Pr(p X > t) = e^{-t}, \quad t >0.
\]
\end{lemma}
\begin{proof}
$\Pr(pX >t) = \Pr(X > t/p)$,
and, since $X$ is an integer, 
\[
\Pr(X > t/p) = \Pr(X \ge \lceil t/p \rceil)
= (1-p)^{\lceil t/p \rceil+1}.
\]
Since $\lim_{n \to \infty}(1+n^{-1})^n = e$,
we have that the last expression converges to $e^{-t}$ as $p \to 0$.
\end{proof}




\end{unit}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\noindent
\hrulefill

\begin{thebibliography}{9}
\bibitem{fg}
{\sc B. Fristedt \& L. Gray}
{\em A Modern Approach to Probability Theory},
Birkh\"auser, 1997.
\bibitem{hs}
{\sc E. Hewitt \& K. Stromberg}
{\em Real and Abstract Analysis},
Springer, 1965.
\bibitem{kf}
{\sc A. N. Kolmogorov \& S. V. Fomin}, 
{\em Introductory Real Analysis}, 
Dover, 1975.
\bibitem{dm}
{\sc D. Mumford},
The dawning of the age of stochasticity.\\
{\tt http://www.dam.brown.edu/people/mumford/Papers/Dawning.pdf}, 1999.
\bibitem{wil}
{\sc D. Williams},
{\em Probability with Martingales},
Cambridge, 1991.
\end{thebibliography}


\end{document}



\def\V{\mathbb{V}}
\def\H{\mathbb{H}}
\def\C{\mathbb{C}}

The following is written WITHOUT USING TRANSFINITE INDUCTION.
Compare with the original approach of Rene Baire (1905).

Approximations de points de limites de fonctions avec discontinuites.

\paragraph{The theorem}
Suppose $(S,d)$ is a complete metric space.
Let $F_1, F_2, \ldots$ be closed sets and suppose
\[
S = \cup_n F_n.
\]
Then one of the $F_n$ must contain an open ball.

\hrulefill

\proof
Suppose none of the $F_n$ contains an open ball.\\
By definition, $S$ contains an open ball.
Then $F_1^c$ is nonempty and contains an open ball.
\[
B_1 \subset F_1^c.
\]
Consider now $F_2^c$. We claim that
\[
B_1 F_2^c \not = \varnothing
\]
because, otherwise, $B_1$ would be contained in $F_2$ and
we assumed otherwise. So $B_1 F_2^c$ is a nonempty open set,
therefore it contains an open ball:
\[
B_2 \subset B_1 F_2^c.
\]
Continuing in the same manner, we find that there exist
nonempty balls $B_n$, such that
\[
B_{n+1} \subset B_n F_{n+1}^c \subset B_n.
\]
By choosing the radii of the balls to be decreasing at
least geometrically, we find that their centres $x_n$ form
a Cauchy sequence, and, by completeness of $S$,
\[
x_n \to x \in S.
\]
But
\[
x \in \cap_n B_n \subset \cap_n F_n^c.
\]
Thus,
\[
x \in S - \cup_n F_n,
\]
contradicting the assumption that $S=\cup_n F_n$.
\qed


\hrulefill



\paragraph{An application}
Consider the set $\N$ and let, for $\epsilon > 0$ and sufficiently small,
\[
I_n(\epsilon) := (n-\epsilon 2^{-n},~ n+\epsilon 2^{-n}),
\quad n \in \N.
\]
We also have
\[
\N \subset \bigcup_{n \in \N} I_n(\epsilon) =: I(\epsilon).
\]
Letting $\epsilon$ range, e.g., over $\Q$, we find that
$I(\epsilon)$ decreases as $\epsilon$ decreases
and
\[
\lim_{\epsilon \downarrow 0} I(\epsilon) 
= \bigcap_{\epsilon > 0} I(\epsilon) = \N.
\]
What is responsible for this is that, for all $\epsilon$
sufficiently small, the closed intervals $I_n(\epsilon)$ are disjoint.
There are no suprises here.

But now let $\V = \Q \cap [0,1]$. This is a countable set:
\[
\V = \{ q_1, q_2, \ldots \}.
\] 
Let
\[
I_n(\epsilon) := (q_n - \epsilon 2^{-n},~ q_n+\epsilon 2^{-n}),
\quad n \in \N.
\]
Again,
\[
\V \subset \bigcup_{n \in \N} I_n(\epsilon) =: I(\epsilon),
\]
and, as $\epsilon$ decreases, so does $I(\epsilon)$.
Let
\[
\H := \lim_{\epsilon \downarrow 0} I(\epsilon)
= \bigcap_{\epsilon > 0} I(\epsilon).
\]
The problem here is that, no matter how small $\epsilon$ is,
the intervals $I_n(\epsilon)$ are not all disjoint.
So we cannot argue that $\V$ equals $\H$. In fact,
\[
\V \not = \H.
\]
The reason is that {\bf $\H$ is uncountable}.\\
To see this, suppose, on the contrary, that $\H$ is countable,
say
\[
\H = \{h_1, h_2, \ldots\}.
\]
Since 
\[
I(\epsilon)^c \subset \Q^c,
\]
each closed set $I(\epsilon)^c$ contains only irrational points
and hence it contains no open set.
On the other hand,
\[
\H^c = \bigcup_{\epsilon \in \Q_+} I(\epsilon)^c.
\]
So, if $\H$ were countable then we would be able to write
\[
[0, 1] = \H \cup \H^c
= 
\bigcup_{i=1}^\infty \{h_i\} \cup \bigcup_{\epsilon \in \Q_+} I(\epsilon)^c,
\]
i.e.\ as a countable union of closed sets none of which contains an
open set. By the Baire category theorem, this violates the
completeness of $[0,1]$. Hence $\H$ is uncountable. But $\V$ is
countable. Hence $\V \not = \H$.

However, we can conclude that $\V$ has Lebesgue measure zero.
Indeed, the Lebesgue measure of $\V$ is smaller than that
of $I(\epsilon)$ which is at most $2\epsilon$. And this is
true for all $\epsilon > 0$.


